浅析排序算法-1 (列举5种)
2022/7/23 1:25:15
本文主要是介绍浅析排序算法-1 (列举5种),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
浅谈几个重要的排序算法,实现数组的升序排序
初始代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define NUM 10 void travel(int *arr,int len,bool sorted=false); int main(void) { int arr[NUM] = {1,9,0,5,7,2,12,54,21,33}; // 测试数组 // 排序函数 travel(arr,NUM,true); // 遍历 return 0; } void travel(int *arr,int len,bool sorted) { for (int i=0;i<len;i++) { printf("%d ",arr[i]); } printf("\n"); }
冒泡排序
比较相邻的元素,如果第一个比第二个大,就交换它们两个,对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这步做完后,最后的元素会是最大的数。针对所有的元素重复以上的步骤,除了最后一个,持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
void bubble_sort(int *arr,int len) { int temp; for (int i=0;i<len-1;i++) { for (int j=0;j<len-i-1;j++) if (arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } }
选择排序
*每次选择最小的,放到应该放的位置
void select_sort(int *arr,int len) { int index; for (int i=0;i<len-1;i++) { index = i; for (int j=i;j<len;j++) { index = arr[index]<arr[j]? index:j; } int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } }
如上所示,每次找到第i个元素后面的最小元素,然后和第i个元素交换
插入排序
将待排数组的第一个元素看成是一个有序数组,然后将一个个其他元素插入到这个数组中,从后往前找插入位置
void insert_sort(int *arr,int len) { int temp,j; for (int i=1;i<len;i++) { temp = arr[i]; for (j=i-1;j>=0 && arr[j]>temp;j--) { arr[j+1] = arr[j]; // 比temp大的元素后移 } // insert arr[j+1] = temp; } }
希尔排序
上述3种排序算法效率都比较低,希尔排序的效率相对较高,在插入排序的基础上再做优化,但并非稳定的算法
先分组,在组内做插入排序,这样可以减少移动元素的次数,组的数量称为步长
void shell_sort(int* arr,int len) { int step = len / 2; while (step) { for (int i=step;i<len;i++) { int temp = arr[i],j; for (j=i-step;j>=0 && arr[j]>temp;j-=step) { arr[j+step] = arr[j]; } arr[j+step] = temp; } step /= 2; } }
每次循环,步长会逐渐减小
基数排序
不同于上述四种基于比较的排序算法,基数排序不基于比较,效率较高,但有所限制条件
void radix_sort(int *arr,int len,int max) { // 开临时数组 int *pTemp = new int[max+1]; // 都赋值为-1 for (int i=0;i<max+1;i++) { pTemp[i] = -1; } for (int i=0;i<len;i++) { pTemp[arr[i]] = arr[i]; } int k = 0; for (int i=0;i<max+1;i++) { if (-1 != pTemp[i]) arr[k++] = pTemp[i]; } delete[] pTemp; }
可以看到这个算法利用了数组下标天然有序的特点
这个排序方法有着如下限制:
- 只能是正整数
- 元素不能重复
- 特别注意内存空间,如果max相当大,显然对内存空间是一个巨大的浪费
最后
以上列举了5种较为简单的排序算法,后续会再详细介绍复杂一点的算法
这篇关于浅析排序算法-1 (列举5种)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-07面向对象编程基础:初学者指南
- 2024-09-07数据结构入门:了解基础概念与简单应用
- 2024-09-07面向对象编程入门:掌握基本概念与实践
- 2024-09-07数据结构入门:从基础概念到基本操作
- 2024-09-07从零开始学数据库:入门级指南与实操技巧
- 2024-09-07综合设备故障分析与预防:实例代码与优化策略
- 2024-09-07数据库入门:轻松掌握数据管理基础
- 2024-09-07面向对象入门:快速掌握对象编程基础
- 2024-09-07数据库教程:入门与实践指南
- 2024-09-07面向对象开发教程 - 从零基础到实践应用的进阶之路