【数据结构初阶】八大排序算法的 “速度与激情”：谁是最快的 “整理大师”？（含复杂度判断及源码）
本文详细介绍了八大排序：直接插入排序，希尔排序，直接选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序，并且介绍了它们的时间复杂度、稳定性及适用场景，为实际应用中选择合适排序算法提供参考
🔥个人主页：爱和冰阔乐
📚专栏传送门：《数据结构与算法》 、C++
🐶学习方向：C++方向学习爱好者
⭐人生格言：得知坦然 ，失之淡然
文章目录
一、排序的概念及其应用
1. 概念
排序: 所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的操作
2.排序的应用
在生活中排序无处不在，它通过将无序信息转化为有序状态，帮助我们更高效地处理数据、解决问题，就比如我们购物时在淘宝上逛，商品可以按价格从高到低，可以按评分排，还可以是商品购买人数的多少排序等等
再比如说浏览器上的热榜排名也是如此
由此可见，排序算法在生活中发挥着极大的作用
二、排序的分类
排序分为两个大类，比较排序和非比较排序，在本文中我们只介绍七大比较排序和非比较排序中的计数排序，比价排序还分为插入排序，选择排序，交换排序，归并排序四类，具体如下
三、直接插入排序
1. 基本思想
直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列
实际生活中我们玩扑克牌时就用了插入排序的思想
思想：
简单来说，一组数组已经是有序了，将在数组中插入一个数据A，那么A就需要和数组中原有的有序数组来比较大小，将A放到数组后形成的新的数组依旧是有序的，下面我将通过一个动图来表达这个思想
2.动图演示
代码思路：
初始情况下，我们认为当前数组中只有一个元素时，数组是有序的
首先我们定义两个变量:
因此我们先定义end指向数组中唯一元素0（即数组中最后一个元素），下标为 a [0]
我们要将数据插入到有序的数组中，因此需要定义tmp保存插入的数据1
排序过程：
1.将end数据和tmp比较，如若end的数据大，就要让end数据往后走走到 a [end+1] 位置，然后让end- -，此时end为a[-1]小于0，数组越界，再让tmp存放到数据放到 a [end+1] = a[0] 位置,然后让end走到有序序列的最后一个位置即 a [1]位置
2.如若tmp数据大，那么就不需要让end数据往后挪动，直接让tmp放到 a [end+1] 的位置即可
注意： 1.这里我们需要注意的是1.循环的结束条件是n-1，因为最后一个数据是tmp，要拿它和排好的数组比较
2.边界的判断，如果end越界或者tmp大于end都跳出循环
代码实现：
//冒泡排序时间复杂度为O（n^2） 当时间复杂度为O（n）时——数组有序
//直接插入排序——当数组有序且为降序的时候时间复杂度为O(n^2)，但是一般的时候时间复杂度小于O（n^2）
void InsertSort(int* arr, int n)
{
//这里只需要让i走到最后一个元素的前一个位置即可，因为最后一个元素时tmp，要拿tmp往前比较插入到排好序的数组中
for (int i = 0; i < n-1; i++)
{
//有序的序列中最后一个数据下标位置
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
//如果遍历到当前数组位置的数据比tmp大，那么就让end存储的数据移动end+1位置，然后让end--走到前一个数据，继续和tmp比较
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
//如果当前数据不大于tmp，则break跳出循环
break;
}
}
arr[end + 1] = tmp;
}
}
3.时间复杂度的判断
由于是双层循环，时间复杂度是O(n^2),当我们要排升序的数组，但是原数组是完全降序数组，那么时间复杂度就是O( n ^2)，正常情况下是小于n ^2的
这里需要注意虽然直接插入排序和冒泡排序的时间复杂度看似一样，但是冒泡排序只当数组有序时为O（n），正常情况下直接插入排序的时间复杂度更好点
四、希尔排序
1.提出原因及其思想
希尔排序是为了解决直接插入排序的最坏情况下：我们要排升序，但是原数组是完全降序时的时间复杂度过高
我们发现将数组划分成二等分，那么就是对n/2的数据进行直接插入排序，时间复杂度绝对小于n^2,因此我们的优化是将数组划分成多组进行直接插入排序，也就是下面的希尔排序
希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：线先选定⼀个整数（通常是gap=n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序
它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的
我们定义gap=5，将数组分为5份（9和4一对，1和8一对），每份都进行直接选择排序，最后排成上图
我们经过上面的一次排序发现如下规律：
1.每组比较的次数少
2.大的数据跑到后面去，小的数据在前面了
我们把上述 第一次排序称为预排序，时间复杂度一定是远远小于O（n^2）
然后我们让gap=n/3+1，也就是5/3=1,1+1=2，下一次排序是将数组分为2组
我们发现gap=2时，数组越来越有序了，我们再让gap=gap/3+1，2/3=0,0+1=1，也就是每间隔一为一组，我们发现当gap>1是预排序，当gap==1时就是直接插入排序算法，最后变成有序数组了
完整的图解：
** 2.证明思路**
注意： 这里的while循环的临界条件必须是大于1，不能等于1，如果等于一1，gap=gap/3+1,如：1/3=0,0+1=1，会死循环，因此必须大于1才行
大家可能疑惑为什么是gap=gap/3+1？
1 gap/2——划分的组多，每组比较的次数少，但是while（gap>1)的循环比较多
2 gap/8——划分的组少，每组比较的次数要多因此要gap/3或者/2
那为啥要+1，因为可能/3后gap为0,而我们必须保证gap为1，所以要+1
** 3.代码实现**
//希尔排序的时间复杂度是0(n^(3/2))
//直接插入排序的弊端：大的数据在前面，小的数据在后面
//当数组为降序序列时，直接插入排序算法该如何优化？
//将数组划分为多组来进行直接插入排序
//1.经过上述划分多组的预排序——小的在前，大的在后面（不是有序的），即gap>1是预排序
//2.gap/3+1，一直到gap==1，是直接插入排序
//希尔排序
void ShellSort(int* arr, int n)
{
//end和end+gap位置数据比较
//gap等于几划分成几组，假设有10个数据，gap=5，则分为5组，每组个数为2
int gap = n;
while (gap > 1)//这里如果条件为>=1，如果等于1，gap/3+1会一直等于1(1/3=0,0+1=1)，一直进入，死循环了
{
//除多少次3就是我们循环的次数，第一次循环除以一个3，第二次已经除了两个3，第3次则3个3，因此可得除了多少次3就要循环多少次
//因此第一层while循环时间复杂度为O（log3n）
gap = gap / 3 + 1;//4 2 1 为什么gap是gap/3+1?
//第一眼看时间复杂度为O(n^2)，但是希尔排序是直接插入排序的优化，因此时间复杂度错误
//这里假设n=9，若gap=3，则一共有gap组，每组n/gap个数据
//我们假设数据均是大数据在前，小数据在后，那么每组挪动次数是1+2（每组有三个数据）
//假设n个数据，一共gap组，每组有n/gap个数据，那么每组挪动的次数1+2+3+……+（n/gap-1）
//由于一共有gap组：所以总的挪动次数为gap*[1+2+3+……（n/gap-1）]
//gap的取值n/3 n/9 n/27 …… 1
//则当gap为n/3时，移动总数为n/3*（1+2）=n，当gap为n/9时，移动总数为n/9（1+2+3……+8）=n/9*8(1+8)/2=4n
//最后一趟（接近有序了），gap==1，直接插入排序，时间复杂度大约为O（n）
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else {
break;
}
}
arr[end + gap] = tmp;
}
}
}
** 4.时间复杂度的判断**
眨眼一看，我们发现希尔排序的时间复杂度不还是O（n^2）吗，但是我们仔细看便发现，由于gap=gap/3+1，除多少次3就是我们循环的次数，第一次循环除以一个3，第二次已经除了两个3，第3次则3个3，因此可得除了多少次3就要循环多少次，因此第一层while循环时间复杂度为O（log3n）。
那么我们来分析下内层循环
通过以上的分析，可以画出这样的曲线图：
因此，希尔排序在最初和最后的排序的次数都为n，即前⼀阶段排序次数是逐渐上升的状态，当到达某⼀顶点时，排序次数逐渐下降⾄n，⽽该顶点的计算暂时⽆法给出具体的计算过程
希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语⾔版)》—严蔚敏书中给出的时间复杂度为：
在本文里我们默认希尔排序的时间复杂度估算是>0(n^(3/2))
五、直接选择排序
** 1.选择排序的思想**
选择排序的思想：
每一次从待排序的数据元素中选出最小（或最大）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
** 2.实现思路：**
上述解释我们可以这样理解
假设我们需要找小数据将其放到最前面，因此定义begin保存小数据，初始情况下begin指向a[0]位置要保存最小数据，再定义mini遍历数组找到最小的数据，直至找到1这个最小数据，然后让begin存放的3和mini的1进行交换
然后我们让begin++来找次小的数据，重复上面步骤，如果找到了，就让其存放在begin位置，在下图中次小的数据时2，让begin存放的5和mini存放的2交换即可，最后让begin++
依次重复上面步骤直至begin走到最后一个数据的前一个位置，因为如果begin等于这里说明该位置数据就应该在这个位置，不需要进入循环来移动
我们发现一次只找一个最小太慢了，我们可以再定义一个变量end来存放最大的数据，初始情况指向a[5],定义maxi来找大，初始图如下
按照上面的思路我们实现代码，通过运行发现并不对
那么这是为啥？因为我们没有考虑到特殊情况下：begin刚好就是最大值，我们来构造一个简单数组来看看
初始下：
找到了最大值9和最小值1，begin位置刚好是最大值，end位置刚好是最小值，我们发现交换完begin和mini变成了1 3 9，然后我们再交换end和maxi，我发现又变成了9 3 1
因此我们发现了问题，我们对此情况特殊处理，让maxi的数据保存mini即可
3. 动图演示
** 4.代码实现**
//选择排序分为直接选择排序和堆排序
//思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
//直接选择排序,时间复杂度为O（n^2）
void SelectSort(int* arr, int n)
{
int begin = 0, end = n - 1;
//while循环时间为n/2
while (begin < end)//不需要考虑=情况，如果begin等于end说明该位置数据就应该在这个位置，不需要进入循环来移动
{
int mini = begin, maxi = begin;//这里不能让mini和maxi为0，因为begin会变，mini要从begin开始
for (int i = begin + 1; i <= end; i++)//n n-1 n-2 n-3 等差数列求和为n
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
//将mini放到begin位置
//将maxi放到end位置
//若maxi和begin刚好在同一位置
//若begin刚好是最大值如;9 3 1,开始情况下，begin在9位置，end在1位置，maxi指向a[0]位置，mini指向a[2]位置，交换mini和begin数据变成1 3 9，再交换maxi和end变回9 3 1
//所以排序结果不对，因此需要特殊处理
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
begin++;
end--;
//第一次进入循环放最大和最小数据，第二次次打大次小数据，以此类推
}
2
}
5.时间复杂度判断
在最外层while循环，要循环n/2次，在for循环里面要循环的次数是等差数列求和也就是n左右，因此可得直接选择排序的时间复杂度是O(n^2)
六、堆排序
堆排序也是选择排序的一种排序，在前面介绍堆的结构中我们对其的代码思路及实现，还有时间复杂度都有了详细的介绍，大家可以点击下面链接跳转
1.堆排序传送门
七、快速排序
** 1.交换排序的思想**
基本思想：所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
交换排序分为：冒泡排序和快速排序，在我们没学排序算法之前，想必大家都知道快速排序算法之快
** 2.快速排序实现思路**
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为止
因此该排序要用到递归
3.hoare版本快排
1.算法思路
1）创建左右指针（right，left指针），确定基准值
2）让right从右向左找出比基准值小的数据，让left从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环
具体步骤可以参考下面的图解：我们初始情况下可以让keyi指向6，然后通过移动保证
1.让基准值到正确的为止
2.基准值左边比其小，右边比其大
初始情况:
第一次找大小，先让right走到比keyi小的位置3，再让left走到比keyi大的数据7位置，如下图
让left和right位置数据交换
再让right- -，left++，二者均走到9位置，再让right- -找比keyi小的数据，走到了3位置，然后让left++找大，但是我们发现left>right,因此left不能继续往后走
当left>right，基准值keyi和right交换位置，数组变成了3 1 2 6 9 7，那么基准值就走到了它该在的位置了，基准值左边均比其小，右边均大于它
然后我们将以keyi为分割线划分成左右两个序列，然后再重复上述步骤，直至所有元素在相应位置停止
思考：
问题1：为什么跳出循环后right位置的值⼀定不⼤于key？
当 left > right 时，即right⾛到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据⼀定不大于key
问题2：为什么left和right指定的数据和key值相等时也要交换？
相等的值参与交换确实有⼀些额外消耗。实际还有各种复杂的场景，假设数组中的数据⼤量重复时，⽆法进⾏有效的分割排序
代码实现
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _QuickSort2(arr, left, right);
//二分
//[left,keyi-1] keyi [keyi+1,right],这是根据基准值keyi划分出来的两个序列
//递归算法时间复杂度的计算：递归的次数*单次递归的时间复杂度，这里递归的次数和二叉树的层数类似，是logn，单次递归的时间复杂度是O（n）
//因此快速排序的时间复杂度是O（nlogn）
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
//找基准值方法
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
++left;
//虽然有两个循环嵌套，但是实际是遍历一遍，因此时间复杂度是O（n）
while (left <= right)
{
//right；从右往左找比基准值小的数据
while (left <= right && arr[right] > arr[keyi])//要不要arr[right]==arr[keyi],要不要交换
{
right--;
}
//找到了比基准值大或者和基准值相等
//left：从左往右找比基准值大的数据
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
//要想right和left交换必须满足left<right,否则可能存在越界情况，无法交换
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
//如果left>right,跳出循环，让keyi和right交换
Swap(&arr[keyi], &arr[right]);
return right;
}
4.挖坑法版本快排
1.思路
创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）
图解：
初始情况下，hole和基准值key指向6位置，left指向key+1位置的1，right指向end-1位置的8
让right从右往左找比基准值小的数据，找到5位置后，将5放入a[0]位置，那么right指向的位置便是新的hole
让left从左往右找大的数据，找到了7，让7填坑，那么7位置便成了新的坑位
重复上述步骤直至right和left相等时就停止走了（重合时正好是坑位），那么就需要拿基准值来填坑，也就是说6走到了其该在的位置，后续依旧重复该步骤
2.动图演示
3.代码实现：
注意这里的挖坑法只是在找基准值的代码需要变化，递归代码不改变
//挖坑法
int _QuickSort1(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
//注意这里不能++left
//后果：基准值 key 对应的位置（arr[hole]）被跳过，后续分区过程中该位置的值可能被覆盖，导致基准值丢失。
//
//
//2.左右指针相遇位置错误
//正确逻辑：左右指针最终应相遇在基准值的正确位置（即所有小于基准值的元素在左，大于的在右）。
//错误逻辑：若初始 left 被增加，指针相遇位置会偏移，导致基准值被放到错误位置。
//
//数组越界风险
//如果数组长度为 1，初始 left = 0，执行 ++left 后 left = 1，超出数组范围，后续访问 arr[left] 会导致越界。
while (left < right)
//这里+“=”
//2. 缺少等号会导致什么问题？
//无限循环：如果数组中存在多个与基准值相等的元素，缺少等号会使指针在这些元素上停止，导致左右指针无法相遇，外层循环无法终止。
//例如：数组[5, 5, 5, 5]，若 right 遇到 5 不移动，会卡在原地，left 也无法移动，最终导致死循环。
//分区错误：相等元素可能被分到错误的一侧，破坏了 “左小右大” 的分区规则，导致排序结果错误。
{
while (left<right && arr[right]>=key)
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] <= key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
** 5.lomuto前后指针版快排（双指针）**
1.思路（改变找基准值的方法）
创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边
解释： 定义prev指向前面，cur指向后面
cur探路，找比基准值小的数据，分两种情况
1.cur指向的数据比基准值要小：++prev，prev和cur数据交换，然后让cur++
2.cur指向的数据不比基准值要小：让cur继续++
直至cur越界，让prev和key交换，那么最后prev指向的数据就是基准值该在的位置
2.动图演示
3.代码实现：
int _QuickSort2(int* a, int left, int right)
{
int prev = left, cur = prev+ 1;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[key], &a[prev]);
return prev;
}
6.非递归版本的快排
1.思路
非递归版本的快速排序需要借助数据结构：栈
初始化栈： 将待排序数组的整个范围（初始左右索引，为 0 和 n-1）压入栈中
循环处理栈：当栈不为空时，执行以下操作：
- 从栈中弹出一个子数组范围（left, right）。
- 对该范围执行分区操作（与递归版相同），找到基准元素的最终位置
- 将 基准值 左右两侧的子范围（left 到 key-1 和 key+1 到 right）压入栈中（注意压入顺序不影响结果，但通常先压较大的子范围以优化栈空间）
分区操作： 选择一个基准元素，将数组分为两部分，左侧元素小于基准，右侧元素大于基准，并返回基准元素的索引（使用双指针法·）
2.代码实现：
void QuickSortNonR(int* arr, int left,int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//只要栈不为空
//取栈顶元素-两次
int begin =StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//对区间[begin,end]找基准值——双指针法
int prev = begin, cur = prev + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
++cur;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//此时基准值的下标就是prev
//根据基准值划分左右序列：[begin,key-1] [keyi+1,end]
//在入栈时必须考虑；keyi+1<end ,key-1>begin,并且不能等于，因为等于的时候在该序列里面就一个数据，不需要再找基准值，没有必要，不用入栈
//先入右序列（先进后出）
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
//后入左序列（后进先出）
if (begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}
7.时间复杂度的判断
时间复杂度毋庸置疑是O(lnogn)
递归算法时间复杂度的计算=递归的次数*单次递归的时间复杂度，这里递归的次数和二叉树的层数类似，是logn，单次递归的时间复杂度是O（n）
但是我们思考下如果数组已经有序或数组全部为相同的数据，时间复杂度会变为O（n^2）
八、冒泡排序
1.算法思想
前⾯在算法题中我们已经接触过冒泡排序的思路了，冒泡排序是⼀种最基础的交换排序。之所以叫做冒泡排序，因为每⼀个元素都可以像小气泡⼀样，根据自身大小⼀点⼀点向数组的⼀侧移动
2.动图演示
3.代码实现
九、归并排序
1.算法思想
其是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。归并排序核⼼步骤
2.代码实现
void _MergeSort(int* arr, int left, int right,int*tmp)
{
//只要不是left>=right说明至少有两个数据
if (left >= right)
{
return;
}
int mid = (left + right) / 2;//这里这种方法可能导致数据过大溢出，有没有更优的方法？int mid = left + (right - left) / 2;
//根据mid划分成两个序列：[left,mid] [mid+1,right]
_MergeSort(arr,left, mid,tmp);
_MergeSort(arr,mid + 1, right,tmp);
//合并：[left,mid] [mid+1,right]
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//定义临时数组的下标
int index = begin1;
while(begin1<=end1 && begin2<=end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//可能存在第一个序列中的数据没有全部放到tmp中
//可能存在第二个序列中的数据没有全部放到tmp中
//这里举个例子，如果数组1存放10，数组2存放6 begin2=end2进入while循环，再进入else语句，把6存放到tmp后，begin2++，大于end，无法再进入循环导致10无法存放到tmp中
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//将tmp中的数据挪回到arr中
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
//归并排序
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1,tmp);
free(tmp);
}
3.时间复杂度
这里排序思想依旧是递归，因此可见时间复杂度是O（nlogn）
十、计数排序
1.算法思想
前面讲述了排序分为比较排序和非比较排序，计数排序就是非比较排序的一种
非比较排序：计数排序,又称鸽巢原理，是对哈希直接定址的变形应用，操作步骤如下：
1.统计相同元素出现次数
2.根据统计的结果将序列回收到原来的序列中
2.代码实现
//计数排序适合range范围较小的情况
void CountSort(int* arr, int n)
{
//count数组中存储的是次数，下标+min对应的是原数组的数据
int min = arr[0], max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
//上述for循环遍历完就知道最大值和最小值了
//这里计算的是要开辟的空间
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail!\n");
}
memset(count, 0, sizeof(int) * range);
//以上两步可以合并为一步：直接用calloc即可
//将arr中元素出现的数据的次数映射到count数组中
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//定义原数组的下标
int index = 0;
//将count中出现的次数还原到原数组中
for (int i = 0; i < range; i++)
{
//将出现数据的次数一直减到0即退出while循环
while (count[i]--)
{
//count数组中存储的是次数，下标+min对应的是原数组的数据
arr[index++] = i + min;
}
}
}
3.时间复杂度
时间复杂度很容易看出是：O(N+range)，空间复杂度O（range）
计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限
十一、八大算法排序算法复杂度及稳定性分析总分析
1.八大排序算法在VS上运行时间比较
我们通过创立数组，里面存放十万个数据来进行判断是否符合其相应的时间复杂度
2.复杂度及其稳定性总结
稳定性的定义：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
十二、八大排序最全源码
十三、总结
本文介绍了八大排序的各个有点，如果把排序算法比作一场 “数据整队大赛”，那每个算法都有自己的 “排兵秘籍”：
直接插入排序像整理手牌，一张张往合适位置塞，虽慢但稳妥；希尔排序是它的 “加速版”，先分组粗排再精细调整，效率翻倍。
直接选择排序像挑队员，每次选出最大最小往两端站，简单直接却不够灵活；堆排序则是 “选手中的高手”，用堆结构快速定位最值，速度飙升
冒泡排序像水中气泡，大的慢慢 “浮” 到队尾，一步一个脚印；快速排序则是 “闪电分组员”，选个基准值一分为二，递归搞定，平均速度最快
归并排序像拼图大师，先拆成小块排好，再一块块拼回完整有序的大图
计数排序最 “特立独行”，不比较只计数，数据范围小的时候，快得让人惊讶。
这些算法各有神通：有的擅长处理小规模数据，有的在海量数据中称王，有的追求稳定，有的专攻速度 —— 就像工具箱里的不同扳手，总有一款适合当下的 “整队任务
十四、后续介绍
在后面我们将介绍在工业上为了解决快速排序在特殊情况下数组中数据大量相同或者完全相同导致快速排序的时间复杂度退化为O(n^2)而出现的三路划分和为了解决快速排序递归太深的问题而出现的自省排序，还有文件的归并排序哦，敬请期待下节分解！！！
纵情码海钱塘涌，杭州开发者创新动！ 属于杭州的开发者社区！致力于为杭州地区的开发者提供学习、合作和成长的机会；同时也为企业交流招聘提供舞台！
更多推荐
77
0- 0
已为社区贡献2条内容
所有评论(0)