【数据结构】八大排序详解
一、排序的介绍
1.1 排序的概念
排序： 什么是排序？排序就是将一组数据按照某种规则重新排列，这个规则可以是升序，降序，当然也可以是我们自己所拟定的规则。 应用场景： 我们在哪里可以接触到排序呢？比较明显的，想想我们平常刷抖音微博的那些热搜词条，为什么总是显示热度高的？是因为排序。比较隐晦的，想想我们平时用微信与qq发消息时，新发的消息总是在最下面，而不会跑到中间去，这是为什么？也是因为排序。
1.2 排序的分类
排序分为比较排序和非比较排序。 比较排序：
非比较排序：计数排序
二、排序算法的实现（以排升序为例）
2.1 插入排序
如其名，插入，将待排序元素按照一定规则插入一个有序序列中，最终形成一个新的有序序列。就像我们打扑克摸牌时。
在这里插入图片描述
2.1.1 直接插入排序
原理：
分界：直接插入排序一般将数组分为已排序和未排序两个部分。初始时，已排序部分只包括数组里的第一个元素，其他元素都是未排序部分。 逐个插入：再逐个将未排序部分中的元素插入到已排序部分中去。直到未排序部分元素为0。
图解： 此图实现的是一个升序的排列，已排序部分呈现黄色，而未排序部分呈现蓝色，绿色则是正在被移动的元素。初始时，只有第一个元素3是黄色，之后未排序的蓝色部分逐个被抽出插入到已排序部分即黄色部分中。如此重复，直到全变为黄色。
在这里插入图片描述
思路： 1.插入一个元素，极可能会把一部分元素向后挤一个位置，这就会覆盖掉我们之前要插入的元素->将待插元素存起来。 2.两个循环，一个实现统共插入几个元素，一个通过将已排序元素与待插元素比较，实现插入的具体过程。 3.用一个变量将已排序部分和未排序部分分隔开来（用于区分）->end。
内层循环演示：
在这里插入图片描述
代码实现：
//直接插入排序
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;//end 是已排序部分末元素的索引
int tmp = arr[end + 1];//将待插入元素存起来
while (end >= 0)
{
if (arr[end] > tmp)//与待排序元素值作比较
{
arr[end + 1] = arr[end];//往后挪
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}时间复杂度：O(N^2)（最差情况）。 执行结果：
在这里插入图片描述
2.1.2 希尔排序
引入：直接插入排序时间复杂度很高，你可能发现，大的元素越靠前，小的元素越靠后，对于升序排列来说，复杂度越高。那我们反过来想想，倘若我们能够做到将大的元素放在后面，小的元素放在前面，是否可以极大的降低时间复杂度？我们如何做到这一点->分区块将大的元素放在后面，小的元素放在前面，再对总体进行排列->引入希尔排序。
介绍：希尔排序通过将原始数组分成多个子数列，进行局部插入排序，逐步减少子序列之间的间隔，最终完成全局排序。
原理：
1.增量分组：根据 gap（增量序列） 将原数组分成多个子数列（方便小的元素更快跳到数组前端）。一般 gap = n / 3 + 1。n 为数组元素个数。 2.对子序列进行插入排序->局部排序。 3.减少 gap 的值，一般为：gap = gap / 3 + 1。重复1、2，最终实现全局排列（gap 为 1时）。
图解： 1、2为预排序，3为直接插入排序。在gap不等于1的时候进行的都是预排序，在等于 1 的时候进行的是直接插入排序。
在这里插入图片描述
代码实现：
//希尔排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//每次循环减少 gap 的值
for (int i = 0; i < n - gap; i++)//对每组子序列进行排列
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)//局部直接插入排序，直到gap = 1
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}- 对于代码里的局部排序，我们可以这样理解，直接插入排序的gap 就相当于是1，只分了一个组，而对于局部排序，我们只需要对 1 进行替换就好。
- 希尔排序时间复杂度很难计算，它接近O(N^1.3)。相比于直接插入排序，时间复杂度大大降低了。 执行结果：
在这里插入图片描述
2.2 选择排序
选择，很好理解，我们需要在未排序部分选择一个最小（或最大）值与未排序部分开头元素进行交换，直到全部有序。 例如：
2.2.1 直接选择排序
只通过寻找未排序部分（蓝色）与未排序部分首元素进行交换：
在这里插入图片描述
改进思路：倘若我们只是选择最小值进行交换，效率未免太低，我们可以同时找最大值与最小值进行交换，减少时间复杂度。排升序，将未排序部分的最小值与未排序部分首元素交换，将未排序部分的最大值与未排序部分尾元素交换。
- 初始时，整个序列都是未排序部分
1.找未排序部分最大值与最小值，分别与未排序部分尾元素与首元素交换。 2.迭代，重复 1，直到全部有序。
图解：
在这里插入图片描述
- 由于我们是先交换的 mini 与 begin 索引的值，所以需要对maxi == begin 这种情况做处理，如果是先交换 maxi 与 end 索引的值，就需要对 mini == end 这种情况做处理。
代码实现：
//交换
void Swap(int* n1, int* n2)
{
int tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
//直接选择排序
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <= end; i++)//寻找最小值
{
if (arr[i] < arr[mini])
{
mini = i;
}
}
for (int i = begin + 1; i <= end; i++)//寻找最大值
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
if (maxi == begin)//处理特殊情况
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin++]);//将最小值与未排序部分首元素交换
Swap(&arr[maxi], &arr[end--]);//将最大值与未排序部分尾元素交换
}
}时间复杂度：O(N^2) 执行结果：
在这里插入图片描述
2.2.2 堆排序
这里可以看博主之前的博客： 堆->堆详解 堆排序->堆排序详解 代码实现：
//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//大堆：<
//小堆：>
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
//大堆: >
//小堆：<
if (arr[child] > arr[parent])
{
//调整
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void HeapSort(int* arr, int n)
{
//建堆——向下调整算法建堆 o(n)
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
//把堆顶元素往后拿（堆排序n*logn）
for (i = n - 1; i > 0; i--)
{
Swap(&arr[0], &arr[i]);
AdjustDown(arr, 0, i);
}
}时间复杂度：O(N * logN)。 执行结果：
在这里插入图片描述
2.3 交换排序
交换排序是一类通过不断交换元素位置最终达成排序目的的排序算法。
2.3.1 冒泡排序
冒泡排序可以参考下图，这里不做细讲：
在这里插入图片描述
- 简单来说，冒泡排序就是每一轮循环通过比较相邻元素的大小把未排序部分最大的一个数放到未排序部分末尾。假设一个数组里有 n 个元素，就有 n - 1 轮循环。
代码实现：
//冒泡排序
void BubbleSort(int* arr, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
Swap(&arr[j], &arr[j + 1]);
}
}
}- 时间复杂度：O(N^2). 执行结果：
在这里插入图片描述
2.3.2 快速排序
介绍：快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌。 1.选取基准值，通常选择数组的最后一个元素、第一个元素或中间元素。 2.分区，将序列分为小于基准值、基准值与大于基准值三个部分。 3.重复一二，直到所有元素排列完毕。
2.3.2.1 递归版本
思路： 1.选择基准元素：通常选择数组的最后一个元素、第一个元素或中间元素。 2.分区操作：将数组分为两部分，左边元素均小于等于基准，右边元素均大于基准。 3.递归排序：对左右子数组递归执行上述步骤，直到子数组长度为1或0。 图解（不包含分区）： 其中分区是用的hoare版本
在这里插入图片描述
代码实现：
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//当不存在区间或区间只有一个元素时返回
{
return;
}
//找基准值并分区
int keyi = _QuickSort(arr, left, right);
//左序列： (left, keyi - 1) 右序列： (keyi + 1, right)
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}递归版本分区有三种方案：分别是1.hoare版本、2.挖坑法、3.lumoto前后指针法
2.3.2.1.1 hoare版本
原理: 1.基准选择：通常选择数组中间或第一个元素作为基准。 2.双指针扫描： 左指针(left)从左侧开始，向右找到第一个 ≥ 基准值的元素。 右指针(right)从右侧开始，向左找到第一个 ≤ 基准值的元素。 交换这两个元素，继续向中间移动，直到两指针相遇。left >= right 时. 3.递归分区：对左右子数组重复上述过程。
图解： 如图，right 从右往左走找小于 key 的值，left 从左往右走找大于key 的值。找到之后且left 在 right 左边的话就交换。
在这里插入图片描述
在这里插入图片描述
代码实现：
//hoare版本
int _QuickSort1(int* arr, int left, int right)
{
int keyi = left;
left++;
while (left <= right)
{
while (left <= right && arr[right] > arr[keyi])//从右往左走，找比基准值要小的
{
right--;
}
while (left <= right && arr[left] < arr[keyi])//从左往右走，找比基准值要大的
{
left++;
}
if (left <= right)
{
Swap(&arr[right--], &arr[left++]);
}
}
Swap(&arr[keyi], &arr[right]);//把基准值放在正确位置
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//当不存在区间或区间只有一个元素时返回
{
return;
}
//找基准值并分区
int keyi = _QuickSort1(arr, left, right);
//左序列： (left, keyi - 1) 右序列： (keyi + 1, right)
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}- 由于我们小循环的循环条件都包含大循环的循环条件，相当于只循环了一遍，所以hoare版本分区时间复杂度是O(N)。
总时间复杂度：O(N * logN)。
两个小点： 我们知道，最理想的基准值是能够恰好二分的，这样递归次数能够实现最小。 1. 那么： while (left <= right && arr[right] > arr[keyi])//从右往左走，找比基准值要小的 while (left <= right && arr[left] < arr[keyi])//从左往右走，找比基准值要大的
- 两个循环后半循环条件不能够加等号，因为当我们遇到跟 key 相等的数时，时间复杂度会提高，可以看下面一个极端情况：
分区只有右半边序列，没有左半边序列：
在这里插入图片描述
2. 快速排序在处理已经排列好的数据的时候，时间复杂度也会提高到O(N^2)，我们应该如何减少这种情况下的时间复杂度？-> 随机选择基准值（对于之后的两种分区方法也同样适用）
//随机索引生成：
int rand_idx = left + rand() % (right - left + 1);
//交换基准值
swap(&arr[rand_idx], &arr[left]);
int keyi = left;
//之后就可以接上原来的代码了2.3.1.2 挖坑法
原理： 1.挖坑：选择一个基准元素，将其值暂存，原位置视为“坑”。 2.填坑：通过双指针（左右指针）从数组两端向中间扫描，将不符合条件的元素填入“坑”中，并形成新的“坑”。当 left == right 的时候停止扫描,将基准值放入坑位. 3.递归：对左右子数组重复上述过程，直到所有元素有序。
图解：
在这里插入图片描述
代码实现:
// 挖坑法
int _QuickSort2(int* arr, int left, int right)
{
//保存基准值
int key = arr[left];
//设置坑
int hole = left;
//当 left == right 的时候停止循环,将基准值放入坑位
while (left < right)
{
//从右往左找比基准值小的值
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;
key = left;
return key;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//当不存在区间或区间只有一个元素时返回
{
return;
}
//找基准值并分区
int keyi = _QuickSort2(arr, left, right);
//左序列： (left, keyi - 1) 右序列： (keyi + 1, right)
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}弊端: 无法处理有重复的数据,会陷入死循环,反复填坑(left 与 right 都走不动). 若将循环后半条件加上 ‘=’ ,可以解决死循环的问题,但是时间复杂度有可能会逼近O(N^2). 可以仅作了解.
2.3.1.3 lomuto前后指针法
原理:创建前后指针,从左往右找比基准值小的数进行交换,直到基准值左边的值都比它小.
方法: 1.创建前后指针：创建 prev 和 cur 两个指针。 2.从前往后找小：cur 会在前面探路（cur++），直到找到一个比基准值小的，prev++，cur 与 prev 的值交换，cur++。 3.放置基准值：直到 cur 越界，这时候将 prev 跟 key 对应的值交换，将基准值放在正确的位置，实现分区。
图解:
在这里插入图片描述
代码实现：
//lomuto前后指针法
int _QuickSort3(int* arr, int left, int right)
{
//设置基准值
int keyi = left;
//设置前后指针
int prev = left;
int cur = prev + 1;
//一轮循环，直到cur 越界时停止
while (cur <= right)
{
//找到了发生交换，后半条件避免发生不必要的交换
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
//将基准值放入正确位置
Swap(&arr[prev], &arr[keyi]);
return prev;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//当不存在区间或区间只有一个元素时返回
{
return;
}
//找基准值并分区
int keyi = _QuickSort3(arr, left, right);
//左序列： (left, keyi - 1) 右序列： (keyi + 1, right)
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}执行结果（三种）：
在这里插入图片描述
2.3.2.2 非递归版本（借助数据结构—栈）
引入：非递归版本可以避免递归版本可能会引发的栈溢出问题，因为递归版本依赖的是系统栈，而非递归版本则是显式栈，能够控制深度。
- 除了借助借助栈，借助队列也能够实现，但在这里不作展示。
思路：递归版本能够不断的去处理左右序列，那么我们非递归版本自然也要实现这一点，如何实现？ 递归版本我们将左右区域作为参数传递，让下一次递归能够处理左右序列，那么非递归版本，我们是不是要做相似的处理？->将分完的左右区域储存起来好方便后续的处理—>借助数据结构—栈。
图解： 要注意的是，由于栈是先进后出，所以我们在取值的时候要注意顺序。
在这里插入图片描述
//快速排序---非递归版本
void QuickSortNoR(int* arr, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!(StackEmpty(&st)))
{
//每次从栈里取两个值，代表我们所处理区间的范围 [begin, end]
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
//找基准值---lomuto前后指针法
int keyi = begin;
int prev = begin;
int cur = prev + 1;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && cur != ++prev)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
//赋值
keyi = prev;
//左区间[begin, keyi - 1] 右区间[keyi + 1, end]
//判断区间是否需要进一步的分区
//左区间
if (begin < keyi - 1)
{
StackPush(&st, begin);
StackPush(&st, keyi - 1);
}
//右区间
if (keyi + 1 < end)
{
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
}
StackDesTory(&st);
}执行结果：
在这里插入图片描述
2.3.2.3 快速排序的优化—三路划分
引入：学完三种分区之后，我们发现 若hoare版本后半循环条件加了等号 以及其他两种排序在遇到重复的数据时，时间算法度会大大提高，那么我们有什么办法可以解决这类问题呢？->三路划分，划分为三个区域：小于基准值的，等于基准值的以及大于基准值的。
方法：是 hoare 版本和前后指针法的融合 1.设置左右指针，left 指向区间最左边，right 指向区间最右边，设置cur 指针指向 left + 1。 2.keyi 默认取left 的值。将 left 和 right 的值分别用变量 begin 和变量 end 保存。 3.cur 在前方探路：
- 若 arr[cur] < arr[keyi], 交换 cur 与 left 索引所对应的值，然后cur++，left ++。
- 若 arr[cur] = arr[keyi]，cur++，不发生交换。
- 若 arr[cur] > arr[keyi], 交换 cur 与 right 索引所对应的值，然后right–，cur 不变。
4.直到 cur > right 为止。 最终分为了三个区间，分别是[behin , left - 1], [left, right], [right + 1，end]，第一个区间的值小于基准值，第二个等于，第三个小于。我们之后只用处理小于基准值和大于基准值的两个区间。
- 为什么 cur 探路第一种情况下交换之后 cur 能够向后移动一位，而第三种情况下不能向后移动？三路划分可以简单概括为小的往前拿，大的往后拿，相等的就跳过。第一种情况下left 对应值一定 = 基准值，互换之后 cur 对应的值便等于基准值，当然要往后移动一位（在cur 遇到与基准值相等的值之前，left 和 cur 指针一直处于前后指针的关系），而第三种情况下我们无法确定 right 对应值与基准值的关系。
图解： 实现一回三路划分：
在这里插入图片描述
代码实现：
//三路划分
void three_way_partition(int* arr, int left, int right)
{
//递归终止条件
if (left >= right)
return;
//设置左右指针
int begin = left, end = right;
int cur = left + 1;
int key = arr[left];
while (cur <= right)
{
if (arr[cur] < key)
{
Swap(&arr[cur], &arr[left]);
cur++;
left++;
}
else if (arr[cur] == key)
{
cur++;
}
else
{
Swap(&arr[cur], &arr[right]);
right--;
}
}
//三个范围： [begin, left - 1] [left, right] [right + 1, end]
//左区间
three_way_partition(arr, begin, left - 1);
//右区间
three_way_partition(arr, right + 1, end);
}执行结果：
在这里插入图片描述
2.4 归并排序
思想： 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
步骤： 1.分解：将数组不断二分，直至每个数组只含有一个元素（自然有序）。 2.合并：将两个有序子数组合并为一个有序数组：
- 使用双指针比较元素，依次选择较小值放入临时数组。
- 将剩余元素直接追加到临时数组末尾。
- 将临时数组拷贝回原数组对应位置。
合并的前提一定是两个有序的子序列。
- 需要创建临时数组，毕竟两个子序列合并完之后的序列我们要找个地方放。 图解：
在这里插入图片描述
动态图解：
2.4.1 递归版本
代码实现：
//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)
return;
//分解
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//合并，两个子序列的区域要保存好
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//排剩余元素
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//拷贝回原数组
//[left, right]
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(1);
}
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}2.4.2 非递归版本
思路： 我们可以借助栈来实现非递归版本，但在这里不作展示，我们自底向上通过迭代来实现非递归版本。 1.初始化子序列大小：起始子数组大小 gap = 1，表示每个元素本身视为一个有序子数组。 2.循环合并直到完全有序:
- 外层循环：控制子数组大小 gap，每次翻倍，直到 gap >= n。
- 内层循环：遍历数组，每次处理两个相邻的子数组，合并后形成更大的有序子数组。
- 合并操作：将 arr[begin1, end1] 和 arr[begin2, end2] 合并到临时数组，再复制回原数组。
3.优化空间使用：使用一个临时数组存储合并结果，减少内存分配次数。
图解：
在这里插入图片描述
在这里插入图片描述
图一所出现的就是第二和第三种情况，在区域越界的情况下，我们需要重新设置区域的范围：
- 区域二完全越界：退出循环，break。
- 区域二部分越界：end2 = n - 1。 当不存在区域二的时候，也不用担心区域一的越界问题，我们又不管它，不会合并，直接退出就行。 第三种会出现就是当数组元素个数为奇数的时候。
代码实现：
// 归并排序的非递归版本
void MergeSortNoR(int* arr, int n)
{
//创建临时数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += gap * 2)
{
//储存要合并子序列范围
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//临时数组索引
int index = begin1;
//处理边界情况
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
//将两个有序子数列合并
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//拷贝回原数组
for (int j = i; j <= end2; j++)
{
arr[j] = tmp[j];
}
}
gap *= 2;//子数组大小翻倍
}
free(tmp);
tmp = NULL;
}执行结果：
在这里插入图片描述
2.4 非比较排序—计数排序
计数排序是一种非比较型整数排序算法，它通过统计元素出现个数来实现排序。其核心思想是将元素值映射到额外数组的下标，统计频率后填充原数组。
步骤： 1.创建临时数组：创建一个大小合适的计数数组，减少空间的消耗。 2.统计频率：遍历原数组，统计各个元素出现的次数，元素值映射到计数数组的下标，技术数组下标对应值为元素出现次数。 3.根据统计结果填充回原数组。
- 创建一个大小合适的临时数组，我们要将原数组中的数据映射到计数数组的下标,就需要找原数组中的最大和最小值。 找最小值的原因： 如果 arr[6] = {10001, 10002, 10003, 10004, 10005, 10006},我们总不可能申请一个空间大小为10006 个 int 大小的内存，需要申请的是 （10006 - 10001 + 1）个 int 大小的内存。即 max - min + 1 个int 大小。还有如果 arr[3] = { -1, -2, -3 },需要申请的是（-1 - (- 3) + 1]个int 大小的内存，这是只凭最大值申请内存所无法实现的。
图解：
在这里插入图片描述
代码实现：
//计数排序
void CountSort(int* arr, int n)
{
//创建计数数组
int max = arr[0];
int min = arr[0];
int i = 0;
for (i = 0; i < n; i++)
{
if (max < arr[i])
{
max = arr[i];
}
if (min > arr[i])
{
min = arr[i];
}
}
int range = max - min + 1;
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc fail");
exit(1);
}
//统计元素出现个数
for (i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//填充回原数组
int index = 0;
for (i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
free(count);
count = NULL;
}时间复杂度：O(N + K),其中 K 是数据范围（最大值与最小值之差）。 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 执行结果：
在这里插入图片描述
三、八大排序复杂度及稳定性分析
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 即：
在这里插入图片描述
就有：
排序方法 | 平均情况 | 辅助空间 | 稳定性 |
|---|---|---|---|
直接插入排序 | O(N^2) | O(1) | 稳定 |
希尔排序 | O(N*logN) ~ O(N^2) | O(1) | 不稳定 |
直接选择排序 | O(N^2) | O(1) | 不稳定 |
堆排序 | O(N*logN) | O(1) | 不稳定 |
冒泡排序 | O(N^2) | O(1) | 稳定 |
快速排序 | O(N*logN) | O(logN) ~ O(N) | 不稳定 |
归并排序 | O(N*logN) | O(N) | 稳定 |
计数排序 | O(N+K)，其中 K 是数据范围（最大值与最小值之差） | O(N+K) | 稳定 |
分析： 1.直接插入排序：B 遇到跟它一样大的 A，它也不会插在 A前面，会乖乖在后面站好。 2.希尔排序：虽然 B 跟A 同一组的时候不想插在 A 前面，但是 B 又怎么能控制在跟 A 同一组之前在其他组不会乱跑的？在其他组跑的时候就可能蹦到 A 的前面去了。 3.直接选择排序：要是 B 跟 A 同样是未排序部分里的最小值，只不过 B 在 A后面，这个时候 B 就要被换到前面去啦。 4.堆排序：就看一个极端例子，推里全是一样的值，要实现推排序，堆顶元素 A 要跟堆尾元素 B 交换，B 就跑到 A 前面去了。 5.冒泡排序：冒泡排序只能左右换，找最大值，要是 B 跟 A 一样大，B 想换都换不了。 6.快速排序：它可跟冒泡排序不一样，左右换可满足不了它，像这中自由度高的交换往往不稳定。就拿hoare 版本来说，它跟直接选择排序的交换很像，B 也一样容易跳到 A 前面。 7：归并排序：归并也是紧挨着的左右序列合并，大小一样的 A 和 B 没有机会能够交换次序，A 左序列，B 在右序列，只要我们认定 A 比 B 大，B 就没有机会。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号