在上一篇文章中我们介绍了队列的相关知识点及进行了专项的练习，在这一篇中我们将学习排序算法。
冒泡排序
冒泡排序是一种简单的排序算法。它重复地比较相邻的两个元素，并将它们按照顺序交换，从而将最大（或最小）元素 “浮” 到数组的末尾。这个过程类似于气泡在水中上浮的过程，因而得名 “冒泡排序”。
适用说明
冒泡排序适用于小规模的数组排序。由于其算法复杂度较高（平均时间复杂度为 O(n^2)），当排序规模较大时，性能会明显下降。因此，对于大规模数据集，更推荐使用其他高效的排序算法，如快速排序或归并排序。
冒泡排序的空间复杂度为O(1)
冒泡排序的比较次数恒为n*(n-1)/2
冒泡排序是一种稳定的排序算法，即具有相同值的元素在排序后的相对位置保持不变。
举个例子：对序列28 19 33 30 26 31使用冒泡排序法进行升序排序，进行第一趟冒泡排序后得到的序列为？ 冒泡排序是两个两个比较，比如1和2比、2和3比 28>19 所以变为 19 28 33 30 26 31 28<33，所以不动 19 28 33 30 26 31 33>30 所以变为 19 28 30 33 26 31 一直冒泡排序，最终就能得到 19 28 30 26 31 33
本文给出C语言冒泡排序的范例：
#include <stdio.h> void bubblesort(int a[],int n)//冒泡排序 { for(int i=0;i<n-1;i++) { for(int j=0;j<n-i-1;j++) { if(a[j]>a[j+1]) { int t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } } void print(int a[],int n) { for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int a[]={12,11,13,5,6}; print(a,5);//输出原数组 bubblesort(a,5); print(a,5); }
插入排序
插入排序(InsertionSort)，一般也被称为直接插入排序。
对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而生成一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
适用说明
插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时插入排序执行的比较和交换次数为n*(n-1)/2，即最坏的情况是 O(n^2)。
插入排序算法是稳定的。
过程图示
假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。
按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
从小到大的插入排序整个过程如图示：
第一轮： 从第二位置的 6 开始比较，比前面 7 小，交换位置。
**第二轮：**第三位置的 9 比前一位置的 7 大，无需交换位置。
**第三轮：**第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。
**第四轮：**第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。
依次比较多次后到最后一个元素。
本文给出C语言插入排序的范例：
#include <stdio.h> void insertsort(int a[],int n)//插入排序 { int i,j,key; for(int i=1;i<n;i++) { key=a[i]; j=i-1; while(j>=0&&a[j]>key) { a[j+1]=a[j]; j=j-1; } a[j+1]=key; } } void print(int a[],int n) { for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int a[]={12,11,13,5,6}; print(a,5);//输出原数组 insertsort(a,5); print(a,5);//输出排序后的数组 }
希尔排序
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。
希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。
它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
适用说明
希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。
过程图示
希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2…1} 来表示。
如图示例：
（1）初始增量第一趟 gap = length/2 = 4
（2）第二趟，增量缩小为 2
（3）第三趟，增量缩小为 1，得到最终排序结果
本文给出C语言希尔排序的范例：
#include <stdio.h> void shellsort(int a[],int n)//希尔排序 { for(int gap=n/2;gap>0;gap/=2) { for(int i=gap;i<n;i++) { int t=a[i]; int j; for(j=i;j>=gap&&a[j-gap]>t;j-=gap) { a[j]=a[j-gap]; } a[j]=t; } } } void print(int a[],int n) { for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int a[]={12,11,13,5,6}; print(a,5);//输出原数组 shellsort(a,5); print(a,5); }
快速排序
快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。
其思想基本上可以总结为以下几个步骤：
1.选择一个基准值：从待排序的数据中选择一个基准值（pivot），通常选择第一个元素、最后一个元素或者中间的元素。
2.分割：将序列中比基准值小的元素移到基准值的左边，比基准值大的元素移到右边。这个过程称为分割操作。
3.递归排序：对基准值左右两边的子序列分别进行递归排序。即重复上述步骤，直到各个子序列的长度为1，排序完成。
4.合并结果：当所有递归调用结束后，整个序列就变成了有序的序列。
快速排序算法不稳定。
举例
有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准）得到的第一次划分结果为： A.{40,38,46,56,79,84} B.{38,46,56,79,40,84} C.{38,79,56,46,40,84} D.{38,46,79,56,40,84} 选A，解析： 46，79，56，38，40，84 l r 因为以46为基准，所以l不动，对r进行分析 84大于46，所以不用动 接着r--，对应40 46，79，56，38，40，84 l r 40小于46，所以将40替换46 40，79，56，38，——，84 l r 接着l++ 40，79，56，38，——，84 l r l对应79，大于40，所以79替换到r的地方 40，——，56，38，79，84 l r 接着r--，对应38 40，——，56，38，79，84 l r 38小于40，所以38替换到l的地方 40，38，56，——，79，84 l r 接着l++ 40，38，56，——，79，84 l r l对应56，大于40，所以56替换到r处 40，38，——，56，79，84 l r 接着r-- 此时l与r位置相同 所以不用替换，直接把基准值46填进去就行
快速排序的平均时间复杂度为O(nlogn)，最好情况下为O(nlogn)，最坏情况下为O(n^2)，空间复杂度O(logn)
代码
#include <stdio.h> // 交换数组中两个元素的值 void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // 对数组进行划分操作 int partition(int arr[], int low, int high) { int pivot = arr[high]; // 选择数组最后一个元素作为基准值 int i = (low - 1); // 初始化较小元素的索引 for (int j = low; j <= high - 1; j++) { // 如果当前元素小于或等于基准值 if (arr[j] <= pivot) { i++; // 较小元素的索引加1 swap(&arr[i], &arr[j]); // 交换arr[i]和arr[j] } } swap(&arr[i + 1], &arr[high]); // 将基准值放到正确的位置上 return (i + 1); } // 快速排序函数 void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); // 对数组进行划分 quickSort(arr, low, pi - 1); // 递归排序划分的左半部分 quickSort(arr, pi + 1, high); // 递归排序划分的右半部分 } } // 测试快速排序算法 int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printf("Sorted array: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
桶排序
桶排序是一种线性时间复杂度的排序算法，适用于元素服从均匀分布的情况。
它的基本思想是将待排序的元素划分为若干个相同大小的区间（桶）。然后对每个桶内的元素进行排序，最后按照桶的顺序依次将各个桶中的元素合并起来。
首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn；
根据mx和mn确定每个桶所装的数据的范围 size，有
size = (mx - mn) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；
求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数cnt，有
cnt = (mx - mn) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；
求得了size和cnt后，即可知第一个桶装的数据范围为 [mn, mn + size)，第二个桶为 [mn + size, mn + 2 * size)，…，以此类推
因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。
对各个桶中的数据进行排序，可以使用其他的排序算法排序，例如快速排序；也可以递归使用桶排序进行排序；
将各个桶中排好序的数据依次输出，最后得到的数据即为最终有序。
桶排序的时间复杂度为O(n+k)，其中k是桶的数量。相当于桶排序的时间复杂度为O(n)
例如，待排序的数为：3, 6, 9, 1
1）求得 mx = 9，mn = 1，n = 4
size = （9 - 1) / n + 1 = 3
cnt = (mx - mn) / size + 1 = 3
2）由上面的步骤可知，共3个桶，每个桶能放3个数，第一个桶数的范围为 [1, 4)，第二个[4, 7)，第三个[7, 10)
扫描一遍待排序的数，将各个数放到其对应的桶中，放完后如下图所示：
3）对各个桶中的数进行排序，得到如下图所示：
4）依次输出各个排好序的桶中的数据，即为：1, 3, 6, 9
可见，最终得到了有序的排列。
代码
#include <stdio.h> #include <stdlib.h> // 桶排序函数 void bucketSort(int arr[], int n) { // 计算数组中最大值和最小值 int max_val = arr[0]; int min_val = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max_val) { max_val = arr[i]; } if (arr[i] < min_val) { min_val = arr[i]; } } // 根据最大值和最小值计算桶的数量 int bucket_num = (max_val - min_val) / n + 1; int** buckets = (int**)malloc(bucket_num * sizeof(int*)); for (int i = 0; i < bucket_num; i++) { buckets[i] = (int*)malloc(n * sizeof(int)); } // 将数组中的元素分配到对应的桶中 for (int i = 0; i < n; i++) { int index = (arr[i] - min_val) / n; buckets[index][i] = arr[i]; } // 对每个桶中的元素进行排序 for (int i = 0; i < bucket_num; i++) { int* bucket_arr = buckets[i]; for (int j = 0; j < n; j++) { for (int k = 0; k < n - j - 1; k++) { if (bucket_arr[k] > bucket_arr[k + 1]) { int temp = bucket_arr[k]; bucket_arr[k] = bucket_arr[k + 1]; bucket_arr[k + 1] = temp; } } } } // 将所有桶中的元素按顺序合并起来 int index = 0; for (int i = 0; i < bucket_num; i++) { int* bucket_arr = buckets[i]; for (int j = 0; j < n; j++) { if (bucket_arr[j] != 0) { arr[index] = bucket_arr[j]; index++; } } } // 释放桶内存空间 for (int i = 0; i < bucket_num; i++) { free(buckets[i]); } free(buckets); } // 测试桶排序算法 int main() { int arr[] = {5, 2, 9, 4, 7, 6, 1, 3, 8}; int n = sizeof(arr) / sizeof(arr[0]); bucketSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
这篇文章中我们介绍了冒泡排序、插入排序、希尔排序、快速排序及桶排序，在下一篇文章中我们将介绍基数排序、计数排序等算法。
