7 快速排序
快速排序算法最早是由图灵奖获得者Tony Hoare设计出来的，是20世纪最伟大的计算机科学家之一。快速排序在求职面试中是最常考的排序算法之一。
其基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。
既然名曰快速排序，在排序速度上至少应该比前面的冒泡，选择和插入排序快，事实的确如此，具体的时间复杂度可以看文章开头的表格。
7.1 快速排序的代码实现
快速排序的代码实现如下。
#include <stdio.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } //交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置， // 此时在它前的数值均小于它 //在它后面的数值均大于它 int Partition(sqList *L, int low, int high) { int pivotkey; pivotkey = L->r[low]; //枢轴初始化 //从两端交替得往中间扫描 while (low < high) { while (low < high && L->r[high] >= pivotkey) high--; swap(L, low, high); //将比枢轴小的值前移 while (low < high && L->r[low] <= pivotkey) low++; swap(L, low, high); //将比枢轴大的值后移 } return low; } void QSort(sqList *L, int low, int hight) { int pivot; if (low < hight) { pivot = Partition(L, low, hight); QSort(L, low, pivot - 1); QSort(L, pivot + 1, hight); } } void QuickSort(sqList *L) { QSort(L, 0, L->length - 1); } int main() { sqList test = { {9,1,5,8,3,7,4,6,2}, 9 }; QuickSort(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
从以上程序中可以看出，在快速排序中，首先要选取枢轴，然后比其小的放在它的前面，比其大的放在后面。让我们分析在Partition函数第一次被调用时的情况。
具体运行情况如下图所示：
具体执行步骤如下：
- 首先要初始化枢轴，然后将数组其最大和最小位置分别标记为
low和high。 - 然后移动
high标记，比枢轴大则移动，直至比枢轴小，然后交换low和high的位置。 - 再移动
low标记，比枢轴小则移动，直至比枢轴大，然后交换low和high的位置。
从此就可以看到在low位置之前的数值都比low所指的数值小，而high未移动，因而暂时不能说明问题，来看第二次循环。
第二次循环伊始，枢轴放在了low的位置。然后执行相同的流程，发现在low之前的数值都比low所指的数值小，而在high所指及其后面位置的数值，均比low所指的大。
而我们函数返回的数值恰好就是low的数值，也就是整个数组的“分水岭”。然后一直递归，也就是对枢轴的前后两个部分做同样的处理，以此类推，直到low==hight，然后调用返回，返回结束，则排序结束。
7.2 快速排序算法总结
作为最经典，也是面试最常考的排序算法之一，在同样的时间复杂度下，快速排序算法既不需要堆排序那么复杂的堆构建过程，也没有归并排序那么高的空间复杂度。被誉为20世纪十大算法之一，确实有其精妙之处。
8 桶排序
8.1 桶排序的代码实现
桶排序的代码实现如下。
#include <stdio.h> #include <malloc.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 #define BUCKETNUM 3 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } void BucketSort(sqList *L) { //定义两个变量分别存储原数组中的最大和最小值 int max = L->r[0]; int min = L->r[0]; for (int i = 1; i < L->length; i++) { if (L->r[i] > max) max = L->r[i]; if (L->r[i] < min) min = L->r[i]; } //根据最大最小值以及桶的个数划分桶里的数据 const int bucket_num = 3; //根据大小将所有数共分为10个区间，属于某个区间的就放入某个桶里 int leng = max - min + 1; //数组元素的区间长度 int bucket_size = leng / bucket_num; //每个桶的数值范围大小 //创建3个桶 int bucket[BUCKETNUM][MAXSIZE]; //记录每个桶中存入数据的数量 int bucket_sum[BUCKETNUM]; //桶的初始化 for (int i = 0; i < BUCKETNUM; i++) { for(int j = 0; j < MAXSIZE; j++) bucket[i][j] = 0; } //计数数组初始化 for (int i = 0; i < BUCKETNUM; i++) bucket_sum[i] = 0; //入桶 for (int i = 0; i < L->length; i++) { int index = (L->r[i] - min) / bucket_size; bucket[index][bucket_sum[index]++] = L->r[i]; //在元素插入桶的时候使用冒泡排序 for (int j = bucket_sum[index] - 1; j > 0; j--) { if (bucket[index][j] < bucket[index][j - 1]) { int temp = bucket[index][j]; bucket[index][j] = bucket[index][j - 1]; bucket[index][j - 1] = temp; } } } //入桶完毕后，就会得到是个有序的桶，顺序访问桶就能得到有序的数组 int arr_index = 0; for (int i = 0; i < bucket_num; i++) { for (int j = 0; j < bucket_sum[i]; j++) L->r[arr_index++] = bucket[i][j]; } } int main() { sqList test = { {99,11,52,83,36,77,4,63,28}, 9 }; BucketSort(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
从以上代码可以看出，整个流程可以分成一下几步：
- 算出待处理序列中的最小值和最大值，并求出取值范围；
- 根据数据的取值范围，求出每个桶可容纳的数值范围大小；
- 创建桶，并初始化；
- 根据每个元素的数值大小分配具体的桶；
- 将元素放入桶中，顺便对该桶中的元素进行排序；
- 将桶内元素取出，即为有序序列。
如下图所示：
注意每个数值应该放入第几个桶，是根据数值的大小 分布情况来定的。所以一下程序非常重要：
//根据大小将所有数共分为10个区间，属于某个区间的就放入某个桶里 int leng = max - min + 1; //数组元素的区间长度 int bucket_size = (leng + bucket_num - 1) / bucket_num; //每个桶的数值范围大小（进一法）
以及：
int index = (L->r[i] - min) / bucket_size;
8.2 桶排序算法总结
桶排序的主要思想是将待排序的数组划分到桶中，至于每个桶中具体的排序算法，可视具体情况而定，桶排序是将数据进行拆分，排序，然后再组合，从而达到了加速的目的。
桶排序的缺点也非常明显，就是对具体数值的大小非常敏感，而当值域很大且分布不均匀时，就会出现桶内数据数量的不均匀，从而导致排序效果变差。比方说下面一组数据：
sqList test = { {99,98,97,8,3,7,4,95,28}, 9 };
在将数据全部放入桶中，出现了下面这种情况：
也就是说，出现了桶的分配不均这种情况，甚至出现空桶。
9 基数排序
虽然基数排序被定义为非比较类排序，但其主要思想还是比较，只不过不是直接比较，而是先将序列记录关键字的各个位位值进行比较，先将个位进行比较和排序，然后是十位，直到关键字最大数值的最高位，从而完成排序。
9.1 基数排序的代码实现
基数排序的代码实现如下。
#include <stdio.h> #include <malloc.h> #include <math.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void RadixSort(sqList* L) { int max = L->r[0]; for (int i = 1; i < L->length; i++) { if (L->r[i] > max) max = L->r[i]; } //开始从个位一直循环到最大数的最高位 int flag = 0; do { //创建十个重复使用的桶 int buckets[10][MAXSIZE]; int buckets_size[10]; for (int i = 0; i < 10; i++) { buckets_size[i] = 0; } //入桶 for (int i = 0; i < L->length; i++) { int index = (int)(L->r[i] / pow(10, flag)) % 10; buckets[index][buckets_size[index]++] = L->r[i]; } //出桶 int arr_index = 0; for (int i = 0; i < 10; i++) { for (int j = 0; j < buckets_size[i]; j++) { L->r[arr_index++] = buckets[i][j]; } } flag++; } while (max /= 10); } int main() { sqList test = { {50,99,11,52,83,36,77,4,63,28}, 10 }; RadixSort(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
此算法的重点在于确定数值和桶的对应关系，也就是下面这行代码：
int index = (int)(L->r[i] / pow(10, flag)) % 10;
还有外层循环的次数，采用do-while循环，也就是说，至少需要进行一轮排序。
然后就是循环的结束条件while(max /= 10)，从而循环次数就是最大数值的位数。
既然基数排序是从个位开始的，我们先来看看个位的排序，也就是第一次入桶和出桶。
从上图可以看出，第一次入桶，直接根据各个数据的个位数值进行排序，个位数值是几就进几号桶，共有10个桶。
进行完第一轮排序后便到了第二轮排序，让我们看看第二轮排序情况。
因为最大的数只有两位，因此只需要进行两轮排序即可。从上图可以看出，经过第二轮排序后，整个排序任务已经完成。
9.2 基数排序算法总结
基数排序也是一种比较好理解的排序算法，但需要注意，只能从低位开始比较，若从高位开始比较，到了低位时就会出现错误（很好理解，可以自己试试）。
若本来需要比较的数值是一样的，则不会改变原来的相对顺序，所以基数排序是一种稳定的排序算法。
10 计数排序
计数排序是最好理解的排序算法之一，只需要记录每个数出现的频率，将其放入一个辅助空间中，然后再逐个取出进行排序。
这种排序方法虽然简单直观，也比较高效。但并非所有的情况都适用，该排序算法适用于待排序数据范围比较集中的情况，如果数值范围较大，则需要较大的辅助空间。
10.1 计数排序的代码实现
计数排序的代码实现如下。
#include <stdio.h> #include <malloc.h> #include <math.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } void CountSort(sqList* L) { int max = L->r[0]; int min = L->r[0]; for (int i = 0; i < L->length; i++) { if (L->r[i] > max) max = L->r[i]; if (L->r[i] < min) min = L->r[i]; } int len = max - min + 1; int* arr_temp = (int*)malloc(sizeof(int)*len); memset(arr_temp, 0, len*sizeof(int)); //将索引全部移位到辅助数组中 for (int i = 0; i < L->length; i++) arr_temp[L->r[i] - min]++; int index = 0; for (int i = 0; i < len; i++) { while (arr_temp[i] > 0) { arr_temp[i]--; L->r[index++] = i + min; } } free(arr_temp); } int main() { sqList test = { {9,1,5,8,3,3,4,6,1,1}, 10}; CountSort(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
运行的示意图如下：
从上图可以看出，运行的原理很简单，就是根据待排序序列的数值分布范围分配内存空间，然后对各个数值进行计数，然后取出即可。
10.2 计数排序算法总结
计数排序简单高效，尤其擅长于范围集中，且数据量大的集合。况且由于保存到辅助空间时相同数值按照先后数据一次存入，所以也是稳定的排序算法。
计数排序和桶排序一样，对待排序序列的具体数值非常敏感，若数值范围较大，则需要很大的内存空间来进行辅助排序。
11 后记
千淘万漉虽辛苦，吹尽狂沙始到金。这应该是工程量最大的一篇文章了，从酝酿到发表用了至少一周时间，而在这过程中，也有很多成长和收获。感谢阅读，愿我们一起成长，一起期待美好的未来！
