常用排序算法的效率对比有何差异？

本文共计3111个文字，预计阅读时间需要13分钟。

排序综述所谓排序，就是将一组记录按照某个关键字的大小，递增或递减的顺序排列起来。排序算法，就是实现这种排列的算法。排序算法在许多领域都有应用，如数据结构、算法设计、数据库管理等。

排序算法的基本思想是：通过比较记录的关键字，按关键字的大小递增或递减的顺序排列记录。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。

冒泡排序：通过比较相邻元素的关键字，若顺序错误则交换它们的位置，重复此过程，直到排序完成。

选择排序：在未排序序列中找到最小（或最大）元素，将其与未排序序列的第一个元素交换，然后继续在剩余未排序序列中寻找最小（或最大）元素，以此类推。

插入排序：将未排序序列中的元素插入到已排序序列的适当位置，直到整个序列排序完成。

快速排序：选择一个基准元素，将序列分为两部分，一部分包含小于基准元素的元素，另一部分包含大于基准元素的元素，然后递归地对这两部分进行快速排序。

归并排序：将序列分为两半，分别对这两半进行归并排序，然后将排序好的两半合并为一个序列。

这些排序算法在各个领域都有广泛的应用，选择合适的排序算法可以提高程序的性能。

排序综述所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据 排序综述

　　所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

冒泡排序法

排序规则

冒泡排序算法的运作如下：（从后往前）1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3. 针对所有的元素重复以上的步骤，除了最后一个。4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

稳定性:冒泡排序是一种稳定排序算法

算法实现

实现思路

算法实现

1 #include 2 #include 3 4 //冒泡排序(升序) 5 void bubbleSort(int *array, int len) //O(n?) 6 { 7 #if 1 8 // 外层 9 for (int i = 0; i 排序规则

　　它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

稳定性:选择排序是不稳定的排序方法 如:[5,5,3]

算法实现

1 #include 2 #include 3 4 //选择排序(升序排列) 5 void selectionSort(int *array, int len) 6 { 7 int min = 0; // 指向最小的元素的位置 8 // 外层循环 9 for (int i = 0; i

插入排序法

排序思想

排序规则

　　每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

稳定性:插入排序是稳定的。

算法实现

1 #include 2 #include 3 4 //插入排序算法(升序排列) 5 void insertionSort(int *array, int len) 6 { 7 int tmp = 0; // 存储基准数 8 int index = 0; // 坑的位置 9 // 遍历无序序列10 for (int i = 1; i = 0; --j)16 {17 // 基准数根有序序列中的元素比较18 if (tmp < array[j])19 {20 // 有序序列元素后移21 array[j + 1] = array[j];22 // 坑的位置23 index = j;24 } 25 }26 // 填坑27 array[index] = tmp;28 }29 } 希尔排序法

排序思想

　　希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

稳定性: 希尔排序是非稳定排序算法。

算法实现

1 #include 2 #include 3 4 //希尔排序 5 void shellSort(int *array, int len) 6 { 7 // 步长 8 int gap = len; 9 while (gap > 1)10 {11 // 步长递减公式12 gap = gap / 3 + 1;13 // 分组, 对每一组, 进行插入排序14 for (int i = 0; i 排序规则

快速排序：挖坑排序+分治法

分治法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

算法实现

1 #include 2 #include 3 4 //快速排序(从小到大) 5 void quickSort(int s[], int l, int r) 6 { 7 if (l < r) 8 { 9 int i = l, j = r;10 // 拿出第一个元素, 保存到x中,第一个位置成为一个坑11 int x = s[l];12 while (i < j)13 {14 // 从右向左找小于x的数15 while (i = x)16 {17 //左移, 直到遇到小于等于x的数18 j--;19 }20 if (i < j)21 {22 //将右侧找到的小于x的元素放入左侧坑中, 右侧出现一个坑23 //左侧元素索引后移24 s[i++] = s[j];25 }26 27 // 从左向右找大于等于x的数28 while (i 排序规则

归并排序: 空间换时间

算法实现

1 #include 2 #include 3 4 //将两个有序数列a[first...mid]和a[mid+1...last]合并。 5 void mergeArray(int a[], int first, int mid, int last, int temp[]) 6 { 7 int leftStart = first; //左有序序列起点 8 int leftEnd = mid; //左有序序列终点 9 int rightStart = mid + 1; //右有序序列起点10 int rightEnd = last; //右有序序列终点11 int length = 0; //两个有序序列合并之后的有序序列长度12 int i = leftStart, j = rightStart;13 14 //将两个有序序列中的元素合并到第三个有序序列中(a的左半部分和右半部分合并到temp中)15 while (i <= leftEnd 21 }22 else23 {24 temp[length++] = a[j++];25 }26 }27 //如果左半部分还有元素, 直接放到temp中28 while (i <= leftEnd)29 {30 temp[length++] = a[i++];31 }32 //如果右半部分还有元素, 直接放到temp中33 while (j <= rightEnd)34 {35 temp[length++] = a[j++];36 }37 //将temp中排好的序列拷贝到a数组中38 for (i = 0; i

效率比较

测试代码

1 #include 2 #include 3 #include //利用时间生成种子 4 #include 5 #include 6 #include "sort.h" 7 8 //效率测试 9 #define NUMBER 3000010 11 //获取系统时间,精确到毫秒12 long long getSystemTime()13 {14 struct timeb t;15 ftime(16 return 1000 * t.time + t.millitm;17 }18 19 //生成随机数20 void randNumber(int* array, int len)21 {22 int i;23 //生成种子24 srand((unsigned)time(NULL));25 for (i = 0; i

运行结果

结论

　　根据效率测试代码运行结果，以上6种排序方式对于30000个数据的排序效率显而易见。