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 后记

千淘万漉虽辛苦，吹尽狂沙始到金。这应该是工程量最大的一篇文章了，从酝酿到发表用了至少一周时间，而在这过程中，也有很多成长和收获。感谢阅读，愿我们一起成长，一起期待美好的未来！

十大经典排序算法（C语言实现）(三)