【数据结构基础】之八大排序(C语言实现）
前言：算法和数据结构是有一定的关联的，八大排序算法在数据结构里算是比较重要的一个部分，今天本篇博客将介绍八大排序算法的原理和实现。
可视化工具及动画演示----旧金山大学（usfca）数据结构可视化工具
📃博客主页： 小镇敲码人
💞热门专栏：数据结构与算法
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏
🌏 任尔江湖满血骨，我自踏雪寻梅香。 万千浮云遮碧月，独傲天下百坚强。 男儿应有龙腾志，盖世一意转洪荒。 莫使此生无痕度，终归人间一捧黄。🍎🍎🍎
❤️ 什么？你问我答案，少年你看，下一个十年又来了 💞 💞 💞
🐧 冒泡排序
♈️ 冒泡排序原理及代码实现
冒泡排序应该我们大家绝大部分人都接触过，因为很简单所以常常出现在教科书中用来启发学生，它重复地访问要排序的元素序列，依次比较两个相邻的 元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。访问元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素序列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到序列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。----部分节选自百度百科
冒泡排序可视化演示及工具
代码实现：
// 冒泡排序
void BubbleSort(int* a, int n)
{
int flag = 0;//设置标志变量优化
for (int i = 0; i < n - 1; i++)//排序n个数，需要n-1趟
{
flag = 0;
for (int j = 0; j < n-i-1; j++)
{
if (a[j] > a[j + 1])//如果满足交换条件交换
{
flag = 1;//如果存在交换，将flag设置为1
Swap(&a[j], &a[j + 1]);
}
}
if (flag == 0)//如果这一趟没有数交换说明已经有序，结束排序
{
break;
}
}
}
- 冒泡排序排n个数（升序），每一趟排完后最大的数（剩下的数里面）都到了正确的位置，所以不用管了。只需要n-1个是因为，后面的数都到了正确的位置，那剩下一个数也一定在正确的位置。
时间复杂度：O（N^2）
♈️ 稳定性分析
冒泡排序是一种稳定的算法排序，首先解释下什么叫做稳定性，稳定性就是在排序中，相同的元素在排序后仍然保持之前的相对位置，就好比1 2 1 4 3，使用冒泡排序升序排列后，那两个1的相对位置会发生变化吗，答案是不会，冒泡排序是相邻的元素你大于我或者你小于我就会交换，等于是不会交换的，所以冒泡排序是一种稳定的排序。
🐧 选择排序
♈️ 选择排序原理及代码实现
选择排序的工作原理（升序）是每次从剩下的元素序列里面找到最小的元素，放到已经有序的序列后面，直到没有元素。选择排序可视化演示及工具
代码实现：
// 选择排序
void SelectSort(int* a, int n)
{
int i = 0;
int j = 0;
int mini = 0;//创建变量，保存当前最小值的下标
for (i = 0; i < n-1; i++)//n-1趟就排完了
{
mini = i;
for (j = i; j < n; j++)
{
if (a[mini] > a[j])//找出目前最小的元素下标
{
mini = j;
}
}
if(mini != i)//如果这个下标不是i位置，就交换
Swap(&a[mini], &a[i]);
}
}
选择排序的时间复杂度也是O(N^2)。
♈️ 稳定性分析
选择排序不是一个稳定的排序，会改变相同元素的相对位置，升序排序序列3 2 3 1 4，我们将1和位置0的3交换，改变相同元素3的相对位置，破坏了稳定性，不稳定。插入可视化演示及工具
代码实现：
// 插入排序
void InsertSort(int* a, int n)
{
//0~end有序
int end = 0;
int i = 0;
while (end < n - 1)
{
int tmp = a[end + 1];
for (i = end; i >= 0; i--)
{
if (a[i] > tmp)
{
a[i + 1] = a[i];
}
else
{
break;
}
}
a[i + 1] = tmp;
end++;
}
}
🐧 插入排序
♈️ 插入排序的原理及代码实现
插入排序，又称为直接插入排序，顾名思义，核心思想肯定是围绕着插入展开，它的原理是：前n-1个元素已经有序的情况下，我将第n个元素正确插入进去，就能保证前n个元素是有序的，就这样走n-1躺就可以将元素序列排成有序。
代码实现：
// 插入排序
void InsertSort(int* a, int n)
{
//0~end有序
int end = 0;
int i = 0;
while (end < n - 1)
{
int tmp = a[end + 1];//插入位置的元素
for (i = end; i >= 0; i--)//调整其到正确位置，将大于tmp的都往整体后挪动一位，然后插入tmp
{
if (a[i] > tmp)
{
a[i + 1] = a[i];
}
else
{
break;
}
}
a[i + 1] = tmp;
end++;
}
}
时间复杂度是O(N^2)。注意：当数组是一个有序序列的时候，插入一个数据的时间复杂度就是O（N）。
♈️ 稳定性分析
插入排序是稳定的排序算法，因为我们只有大于待插入的值才会将其往后挪动覆盖，小于等于就结束挪动了，没有改变相同元素的相对位置。
🐧 希尔排序
♈️ 希尔排序的原理及其代码实现
希尔排序是插入排序的一种，在性能上比直接插入排序更为优秀，又称“缩小增量排序”（Diminishing Increment Sort），它的原理是
预处理+直接插入排序。希尔排序可视化演示及工具
下面我们来具体分析一下希尔排序的原理：
我们一步步来，下面我们实现（gap为2时的）多组排序。
//gap为2时的预处理
int gap = 2;
for (int i = 0; i < gap; i++)//一共有gap组
{
int end = i;//将end赋值为这组的初始位置下标
while (end < n - gap)//这是一组的直接插入排序，多组的在外面套一个循环就行
{
int tmp = a[end + gap];
int j = 0;
for (j = end; j >= 0; j -= gap)
{
if (a[j] > tmp)
{
a[j + gap] = a[j];
}
else
{
break;
}
}
a[j + gap] = tmp;
end += gap;
}
}
仔细比对，gap等于1时，这个就是我们的直接插入排序。很多教材上也会这样去写，这两种代码的实际效果是等价的。这个就相当于上一组的直接插入排序还没排完，就来排另外一个，只不过调换了下顺序。
int gap = 2;
for (int end = 0; end < n-gap; end++)//多组同时插入排序
{
int tmp = a[end + gap];
int j = 0;
for (j = end; j >= 0; j -= gap)
{
if (a[j] > tmp)
{
a[j + gap] = a[j];
}
else
{
break;
}
}
a[j + gap] = tmp;
}
这个实现了我们来探讨一下gap到底应该取多少？
最终的希尔排序代码：
// 希尔排序
void ShellSort(int* a, int n)
{
int gap = n;//令gap等于n
int i = 0;//i为控制每次插入排序的开始的位置的变量
int j = 0;//j为每次直接插入排序的变量
while (gap > 1)
{
gap = gap / 3 + 1;//gap不为一个固定的值，预处理多次，让我们的分组插入的效果更加好，降低后面直接插入的时间
for (i = 0; i < n - gap; i++)//gap为某一个值时的分组插入，这里我们使用多组同时走插入排序
{
int end = i;
int tmp = a[end + gap];
for (j = end; j >= 0; j -= gap)
{
if (tmp < a[j])//小于就把大的值往后移
{
a[j + gap] = a[j];
}
else//找到了，break
{
break;
}
}
a[j + gap] = tmp;//将tmp赋值给正确位置
}
}
}
♈️ 希尔排序的时间复杂度分析
根据大量的实验算出，希尔排序算法的时间复杂度是约为N^1.3，约差于N*logN，但是已经比直接插入排序好太多了，看来预处理虽然看起来复杂还是很有必要的。
下面我们来画图分析一下它的时间复杂度的计算：
♈️ 稳定性分析
希尔排序是不稳定的排序，直接插入排序是稳定的排序，但是希尔排序的预处理是分组直接插入排序，可能会改变相同元素的相对顺序，是不稳定的排序。
🐧 堆排序
堆排序我们在数据结构堆中已经具体的介绍过这里不再重复叙述。堆排序可视化演示及工具
代码实现：
// 堆排序
void AdjustDown(int* a, int n, int root)
{
int child = root * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child+1])//找出最大的孩子
{
child = child + 1;
}
if (a[root] < a[child])//如果根节点的值比最大的孩子小就交换
{
Swap(&a[root], &a[child]);
root = child;
child = root * 2 + 1;
}
else//否则调整完成
{
break;
}
}
}
//堆排序,向下调整
void Heapsort(int* a, int n)
{
assert(a);
for (int i = (n-1-1)/2; i >= 0; i--)//我们向上调整，原地建一个大堆
{
AdjustDown(a,n,i);
}
//将大堆最大的和最后一个元素交换，并向下调整
for (int end = n - 1; end >= 0; --end)
{
Swap(&a[0], &a[end]);//将堆顶元素放到堆最后面去
AdjustDown(a,end,i);//此时的end就代表我们的元素个数
}
}
堆排序的时间复杂度O(NlogN)。建堆的消耗是O(N)，排序的过程是NlogN。
♈️ 稳定性分析
堆排序不是一个稳定的算法，我们使用下面的例子来解释一下。
🐧 归并排序
归并排序的原理在于两个字，归和并，也对应两个操作步骤，递归和合并，其中递归也包含着分治的思想 ，即把一个相同的问题，划分为很多一样的子问题来解决，下面我们来归并排序的归并排序可视化演示及工具
♈️ 归并排序递归版本
画图分析：
我们在写递归代码的时候，应该申请一个和原数组一样大小的tmp数组，用于辅助合并，因为两个子数组比较之后，需要把小的那个值放到一个地方，如果放到原先的数组里面就可能会覆盖我们的值，合并完之后在把left~right这段区间排好的值拷贝到原数组，好进行下一大组的比较。
代码实现：
void MergeSort1(int* a, int* tmp, int left,int right)
{
if (left >= right)//如果左边界大于右边界就可以返回了，没有划分的余地了，但是要考虑一种特殊情况，就是只有一个数据的情况
return;
int mid = left + (right - left) / 2;
MergeSort1(a, tmp, left, mid);//分割左子数组
MergeSort1(a, tmp, mid + 1, right);//分割右子数组
//左右两边的数组已经有序，我们进行合并操作
int idx = left;
int begin1 = left;
int end1 = mid;
int begin2 = mid + 1;
int end2 = right;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[idx++] = a[begin1++];
}
else
{
tmp[idx++] = a[begin2++];
}
}
//处理还没有遍历完的数组，把他们加到数组的后面
while (begin1 <= end1)
{
tmp[idx++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[idx++] = a[begin2++];
}
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));//将已经排好序的，再拷贝到原数组
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);//开一个辅助数组，用于辅助我们的合并操作
if (tmp == NULL)//如果申请空间失败直接返回
{
perror("malloc failed");
exit(-1);
}
MergeSort1(a,tmp,0,n-1);//递归，进行归并排序
free(tmp);//释放空间
tmp = NULL;//置空
}
♈️ 归并排序非递归版本
我们写了递归的版本，就应该思考一下如何写出它的非递归版本。
代码实现：
void MergeSort2(int* a, int* tmp, int n)
{
int gap = 1;//一路开始是11合并
while (gap < n)
{
for (int i = 0; i < n; i += gap * 2)//每次要合并的元素是gap*2，假设有这么多元素
{
//定义两个合并区间的左右边界
int begin1 = i;
int end1 = i + gap-1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)//如果已经没有两个区间合并，那么就无法合并了，跳出循环
{
break;
}
if (end2 >= n)//如果只是第二个区间的右边界超出范围，那么就仍然可以合并，将其右边界设置为数组的最后一个值的下标就行
{
end2 = n - 1;
}
int idx = i;//开始合并
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[idx++] = a[begin1++];
}
else
{
tmp[idx++] = a[begin2++];
}
}
while (begin1 <= end1)//哪个还有剩余就把哪个加到tmp中对于这段区间的后面
{
tmp[idx++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[idx++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//将已经排好序的这段区间重新拷贝到原数组区间，准备下一次合并
}
gap *= 2;//开始下一轮合并
}
}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);//创建辅助数组，存某一段区间排好序的数据
if (tmp == NULL)//如果申请空间失败就退出程序
{
perror("malloc failed");
exit(-1);
}
MergeSort2(a, tmp,n);//进入归并排序
free(tmp);//释放空间
tmp = NULL;//置空
}
♈️ 归并排序的时间复杂度和空间复杂度分析
归并排序不像希尔排序，存在前面的预处理对后面的分组排序是有优化的问题，时间复杂度非常好算，我们画图来分析：
♈️ 稳定性分析
先说结论，归并排序是一个稳定的排序。
🐧 快速排序
快速排序，和它的名字一样，它确实很快。它是冒泡排序算法的改进，通过多次比较和交换来实现。下面我们来具体介绍一下，它的原理和代码实现。快速排序可视化演示及工具
♈️ 快速排序递归实现(Hoare版本-----多坑版)
快速排序是Hoare这个人在1962年提出的一种二叉树结构的交换排序算法，我们先来学习一下这个经典的版本。
它的思想是这样的：
代码实现(递归)：
int PartSort1(int* a, int left, int right)
{
int keyi = left;//记录关键元素的位置，方便最后的交换
while (left < right)//如果left < right就退出循环
{
while (left < right && a[right] >= a[keyi])//先找小（严格找小），也要加上left < right的条件，防止越界
{
right--;
}
while (left < right && a[left] <= a[keyi])//再找大（严格找大），同样的越界条件要加上
{
left++;
}
Swap(&a[left], &a[right]);//找到了交换
}
Swap(&a[keyi], &a[left]);//最后交换keyi元素和最后一个小的元素的位置，这样单趟就排完了，keyi位置的元素到了正确位置，不用管它了
return left;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)//一个元素或者区间不存在的情况递归就结束
return;
int mid = PartSort1(a, left, right);//[left，mid-1] mid [mid+1,right]
QuickSort(a, left, mid - 1);//继续递归左边，执行相同的单趟排序的思路
QuickSort(a, mid + 1, right);//继续递归右边，执行相同的单趟排序的思路
}
为什么说Hoare版本的快速排序存在着很多坑呢，我们画图来分析一下：
递归的这个过程我们也浅浅的画个图来分析一下吧。
我们来解释一下这里为什么一定要右边先找比key小的值：
♈️ 快速排序递归实现（挖坑法）
前面我们介绍了Hoare版本的快速排序，但是坑比较多，后面有人对其在思路上做了优化更好理解了。
我们画图来介绍一下：
代码实现：
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int key = a[left];//保存left位置的值
int hole = left;//保存坑位的下标
while (left < right)//结束条件
{
while (left < right && a[right] >= key)//严格找小
{
right--;
}
a[hole] = a[right];//把小的值放到坑位
hole = right;//更新坑位
while (left < right && a[left] <= key)//严格找大
{
left++;
}
a[hole] = a[left];//把大的值放到坑位
hole = left;//更新坑位
}
a[hole] = key;//把key值赋给相遇时的坑位
return hole;//返回最后key值的下标
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)//一个元素或者区间不存在的情况递归就结束
return;
int mid = PartSort2(a, left, right);//[left，mid-1] mid [mid+1,right]
QuickSort(a, left, mid - 1);//继续递归左边，执行相同的单趟排序的思路
QuickSort(a, mid + 1, right);//继续递归右边，执行相同的单趟排序的思路
}
♈️ 快速排序递归实现（前后指针法）
前后指针法也是快速排序的一种实现思路，我们也来介绍一下。
画图分析：
代码实现：
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int keyi = left;//保存key值的下标
int prev = left;//prev指向小于等于key的指针
int cur = prev + 1;//cur找小，找到了交换，没找到后移
while (cur <= right)//这是程序继续的条件
{
if (a[cur] < a[keyi] && ++prev != cur)//防止相同的值交换
{
Swap(&a[cur], &a[prev]);
}
++cur;//不管哪种情况，cur都要++
}
Swap(&a[prev], &a[keyi]);//最后别忘了把key值和pre交换
return prev;//返回key的正确下标
}
♈️ 快速排序非递归实现
下面我们来看一下快速排序的非递归如何实现，递归有栈溢出的风险，所以一个优秀的程序员应该具备把递归转为非递归的能力。
老规矩画图分析：
代码实现：
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
Stack ps;//创建栈对象
StackInit(&ps);//初始化栈对象
StackPush(&ps, right);//入根节点的区间值，先入右，再入左，这样我们拿的时候就可以先拿到左
StackPush(&ps, left);
while (!StackEmpty(&ps))//如果栈为空，排序完成
{
int left1 = StackTop(&ps);//拿到栈顶区间的左边边界
StackPop(&ps);//pop掉左边边界
int right1 = StackTop(&ps);//拿到栈顶区间的左边边界
StackPop(&ps);//pop掉右边边界
int mid = PartSort3(a, left1, right1);//走一趟快速排序，哪个版本都可以，这里我们用的前后指针
if (right1 > mid + 1)//先入右边区间，如果右边区间存在且长度不为1的话
{
StackPush(&ps,right1);
StackPush(&ps, mid + 1);
}
if (left1 < mid - 1)//再入左边区间，如果左边区间存在且长度不为1的话
{
StackPush(&ps, mid-1);
StackPush(&ps, left1);
}
}
StackDestroy(&ps);//销毁栈
}
♈️ 快速排序的三个优化
🎀 三数取中
正常情况下，我们单趟排序排完最理想的情况是那个key值每一次都是中位数，这样左右两边就均衡了，递归的最深层数是logN，但是如果数组是一个有序数组呢？那每一次key值如果选第一个递归的层数不就是N层了，每一次调整要O(N)，那么就是O(N^2)的时间复杂度，太慢了，我们使用三数取中来优化一下。
三数取中就是在left、right、mid三个位置取一个中位数，然后把它和left位置的值交换，让它来作为key值，这样就不害怕有序的情况了。
代码实现：
int get_mid(int* a, int left, int right)
{
int mid = (left + right) / 2;//中间下标的数
if (a[left] < a[mid])//如果left位置的值小于mid位置的值
{
if (a[mid] < a[right])//如果right位置的值大于mid位置的值，那么mid位置的值就是第2大的（中位数）
{
return mid;
}
else if (a[left] > a[right])//left位置的值大于right位置的值，mid是最大的
{
return left;
}
else
return right;
}
else//a[left] >= a[mid]
{
if (a[mid] > a[right])//mid位置的值大于right位置的值
return mid;
else if (a[left] < a[right])//left不是最大的
return left;
else
return right;
}
}
加在单趟里面是这样的：
int PartSort1(int* a, int left, int right)
{
int mid = get_mid(a, left, right);//三数取中找中位数
Swap(&a[mid], &a[left]);//交换
int keyi = left;//记录关键元素的位置，方便最后的交换
while (left < right)//如果left < right就退出循环
{
while (left < right && a[right] >= a[keyi])//先找小（严格找小），也要加上left < right的条件，防止越界
{
right--;
}
while (left < right && a[left] <= a[keyi])//再找大（严格找大），同样的越界条件要加上
{
left++;
}
Swap(&a[left], &a[right]);//找到了交换
}
Swap(&a[keyi], &a[left]);//最后交换keyi元素和最后一个小的元素的位置，这样单趟就排完了，keyi位置的元素到了正确位置，不用管它了
return left;
}
🎀 小区间优化
这里我们使用插入排序，因为插入排序每一次排序执行的次数不是完整的等差数列，它比冒泡排序和选择排序都要优秀，希尔排序在数据量小的情况下和插入排序差不多，归并排序有空间消耗，堆排序需要建堆，综合考虑我们使用插入排序来进行小区间优化。
//快速排序小区间优化
void QuickSort(int* a, int left, int right)
{
if (right - left + 1 > 10)//区间长度大于10，去走递归
{
int mid = PartSort1(a, left, right);//[left，mid-1] mid [mid+1,right]
QuickSort(a, left, mid - 1);//继续递归左边，执行相同的单趟排序的思路
QuickSort(a, mid + 1, right);//继续递归右边，执行相同的单趟排序的思路
}
else//区间长度小于10，去走插入排序
{
InsertSort(a + left, right - left + 1);
}
}
这里为什么是a+left呢？因为每个大区间不断的去分割，在很多位置都会产生长度小于10的区间：
排序这个小区间的数组，需要传它初始值的地址。
🎀 三路划分加随机取数
但是即使我们做了上面两种优化，也仍旧不够，下面的OJ题使用我们的优化版本就过不了。
912.排序数组
这里我们几乎上面的所有优化都用到了，提交看看结果如何：
这种重复值的情况，确实让我们的快排很难受，因为时间复杂度会到O(N^2)，下面我们介绍第三种优化：
三路划分。
画图分析：
代码实现：
//三路划分
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
return;
int mid = get_mid(a, left, right);//三数取中找中位数
Swap(&a[mid], &a[left]);//把那个中位数放到最左边
int key = a[left];
int begin = left;//保存左边界
int end = right;//保存右边界
int cur = left + 1;//定义cur，用于遍历
while (cur <= right)
{
if (a[cur] < key)//如果小于key
{
Swap(&a[cur], &a[left]);
cur++;
left++;
}
else if (a[cur] > key)//如果大于key
{
Swap(&a[cur], &a[right]);
right--;
}
else
{
cur++;
}
}
QuickSort1(a, begin, left - 1);//递归左边区间
QuickSort1(a, right + 1, end);//递归右边区间
}
提交结果：
可以看到还是过不了，所有用例的都通过了，但是加起来时间仍然太长了，这个时候我们可以猜到，力扣对快速排序做了一些针对，我们对三数取中部分继续优化：
因为我们三数取中取mid、left、right三个位置数中的中位数，如果测试用例故意针对，每次让我们取到次小的数，那么我们递归的深度还是会很大，所以我们需要优化，mid不在取中间位置的数，而是取left~right区间的随机下标，这样它就无法针对我们了。
三数取中优化：
int get_mid(int* a, int left, int right)
{
int mid = left+rand()%(right-left+1);//left~right随机下标的数
if (a[left] < a[mid])//如果left位置的值小于mid位置的值
{
if (a[mid] < a[right])//如果right位置的值大于mid位置的值，那么mid位置的值就是第2大的（中位数）
{
return mid;
}
else if (a[left] > a[right])//left位置的值大于right位置的值，mid是最大的
{
return left;
}
else
return right;
}
else//a[left] >= a[mid]
{
if (a[mid] > a[right])//mid位置的值大于right位置的值
return mid;
else if (a[left] < a[right])//left不是最大的
return left;
else
return right;
}
}
我们再加上随机数种子，这题就可以过了！
加上小区间优化会更快。
♈️ 快速排序时空复杂度分析
快速排序由于我们可以进行一系列的优化，像三路划分、三数取中（随机数）、小区间优化等来避免最坏的情况，让树的高度控制在ogN内，又因为每趟排序的时间复杂度是O(N),所以每层的也是O（N）,最远是logN层，所以时间复杂度是N*logN。至于空间复杂度，递归是会消耗栈空间的，同样的经过优化可以到logN级别。
♈️ 稳定性分析
快速排序不是不稳定的排序。因为它的性能很快，牺牲了稳定性，我们以Hoare版本来举个例子：
🐧 计数排序
计数排序是一个特殊的排序，它在有时候性能很优秀，我们有必要去了解一下它。计数排序可视化工具及演示
♈️ 原理及代码
我们还是画图来分析：
代码实现：
// 计数排序
void CountSort(int* a, int n)
{
int max = a[0];
int min = a[0];
for (int i = 0; i < n; i++)//找最大最小值
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min = a[i];
}
}
int range = max - min + 1;//求出元素的范围
int* count = (int*)malloc(sizeof(int) * range);//动态申请空间
if (count == NULL)//如果申请失败
{
perror("malloc failed");
exit(-1);
}
memset(count, 0, sizeof(int) * range);//初始化count数组
for (int i = 0; i < n; i++)//遍历数组，计数
{
count[a[i] - min]++;
}
int index = 0;
for (int i = 0; i < range; i++)//映射覆盖元素
{
while (count[i]--)
{
a[index++] = i + min;
}
}
free(count);//释放堆上的空间
count = NULL;//指针置空
}
♈️ 时空复杂度
我们看一个算法的时空复杂度不能简单的看它套了几层循环，像刚刚的那个计数排序的时间复杂度就是
O(N+range).其中range代表数组中元素的范围。
这里range不能忽略，因为不知道元素的范围和N比谁大，当range <= N时，这个算法还算可以，但是当range >> N，这个算法的性能就不行了。而且计数排序只能排整数。空间复杂度是O(range)。所以计数排序只适用于小数据范围的排序。是小数据范围，而不是小数据规模。
♈️ 稳定性分析
计数排序是稳定的排序，在排结构体时，如果是排的是其中一个整形数据是可以做到让其它结构体成员稳定的，具体大家可以看看这篇技术博客，写的不错，博主就不在这里分析了。
🐧 内排序与外排序
内排序是指在内存中排序，外排序是指的是可以在磁盘中排序。
🐧 性能测试与排序正确性测试
♈️ 正确性测试
借助这个OJ题来测试一下我们七大排序算法的正确性：
🎀 冒泡排序
这里我们的冒泡排序过了9组测试用例，说明其排序的功能没啥问题，就是太慢了。
🎀 选择排序
选择排序也是同样的效果。
🎀 插入排序
同为一个量级的排序算法，我们的插入排序居然过了11组数据！
🎀 希尔排序
我们的希尔排序直接狠狠拿下了！果然O(N*logN)级别的排序算法就是不一样（崇拜。
🎀 堆排序
堆排序也直接过了！
🎀 快速排序
这里我们快速排序被针对了，导致很慢！还是我们优化了很多地方才过的。
🎀 归并排序
归并排序也过了！
🎀 计数排序
可以看到我们计数排序的实力还是杠杠的，当然这是因为力扣的测试用例没有针对计数排序，如果将数据范围搞的很极端，计数排序的性能就更不上了。
♈️ 性能测试
我们使用下面的代码来测试一下八大排序的性能，测性能的时候我们要调到Release版本下，优化更好。
void TestOP()
{
int N = 10000;
printf("N: %d\n", N);
int* a1 = (int*)malloc(sizeof(int) * N);
if (a1 == NULL)
{
printf("a1 malloc failed\n");
exit(-1);
}
int* a2 = (int*)malloc(sizeof(int) * N);
if (a2 == NULL)
{
printf("a2 malloc failed\n");
exit(-1);
}
int* a3 = (int*)malloc(sizeof(int) * N);
if (a3 == NULL)
{
printf("a3 malloc failed\n");
exit(-1);
}
int* a4 = (int*)malloc(sizeof(int) * N);
if (a4 == NULL)
{
printf("a4 malloc failed\n");
exit(-1);
}
int* a5 = (int*)malloc(sizeof(int) * N);
if (a5 == NULL)
{
printf("a5 malloc failed\n");
exit(-1);
}
int* a6 = (int*)malloc(sizeof(int) * N);
if (a6 == NULL)
{
printf("a6 malloc failed\n");
exit(-1);
}
int* a7 = (int*)malloc(sizeof(int) * N);
if (a7 == NULL)
{
printf("a7 malloc failed\n");
exit(-1);
}
int* a8 = (int*)malloc(sizeof(int) * N);
if (a8 == NULL)
{
printf("a8 malloc failed\n");
exit(-1);
}
for (int i = 0; i < N; ++i)
{
a1[i] = rand() % N;
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
}
int begin1 = clock();
BubbleSort(a1, N);
int end1 = clock();
int begin2 = clock();
SelectSort(a2, N);
int end2 = clock();
int begin3 = clock();
InsertSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4,N);
int end4 = clock();
int begin5 = clock();
QuickSort1(a5,0,N-1);//三路划分版本
int end5 = clock();
int begin6 = clock();
ShellSort(a6, N);
int end6 = clock();
int begin7 = clock();
MergeSort(a7, N);
int end7 = clock();
int begin8 = clock();
CountSort(a8, N);
int end8 = clock();
printf("BubbleSort：%dms\n", end1 - begin1);
printf("SelectSort：%dms\n", end2 - begin2);
printf("InsertSort：%dms\n", end3 - begin3);
printf("HeapSort：%dms\n", end4 - begin4);
printf("QuickSort1：%dms\n", end5 - begin5);
printf("ShellSort：%dms\n", end6 - begin6);
printf("MergeSort：%dms\n", end7 - begin7);
printf("CountSort：%dms\n", end8 - begin8);
}
int main()
{
srand(time(NULL));
TestOP();
return 0;
}
函数clock()是返回程序运行到当前指令的时间：
这是1w整形数据的运行结果：
这是10w整形数据的运行结果：
可以看到10W个O(N^2)的排序就有点hold不住了,特别是我们的冒泡排序，居然跑了14秒！
这是100w整形数据的运行结果：
O(N^2)的算法跑太慢了，我们就不让它们上场了。
这是1000w整形数据的运行结果：
这是1亿整形数据的运行结果：
可以看到1亿整型数据除了我们的快速排序和计数排序稳在10秒内，其它N*logN级别的排序算法都超过了10秒，HeapSort更是达到了惊人的41秒多，其它O(N^2)的算法都上不了桌，这里可能出现内存不够用的情况，把编译器调到64位就行。
![[ROS 系列学习教程] rqt可视化工具箱 - Topic工具](https://img-blog.csdnimg.cn/direct/b61045e6110c4a5a822bd3ef7cbdfb1c.png#pic_center)
