前言
本片博客主要讲解一下八大排序算法的思想和排序的代码
💓 个人主页：普通young man-CSDN博客
⏩ 文章专栏：排序_普通young man的博客-CSDN博客
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
目录
引言
排序的概念
基本概念
常见排序算法分类
排序的运用
冒泡排序（Bubble Sort）
算法原理与步骤
动态演示或图解
代码实现（C语言）
时间复杂度与空间复杂度分析
适用场景与局限性
选择排序（Selection Sort）
原理与实现
性能分析
插入排序（Insertion Sort）
算法描述
实现
性能
时间复杂度
空间复杂度
希尔排序（Shell Sort）
分组插入的概念
实现
复杂度分析
归并排序（Merge Sort）
分治思想的应用
递归实现与迭代实现对比
1. 分解（Divide）
2. 解决（Conquer）
3. 合并（Combine）
非递归版本具体思路：
稳定性与效率
快速排序（Quick Sort）
分区操作详解
递归
快速排序基本思想
“三数取中”策略的引入
前后指针法
三数取中
挖坑法
非递归
堆排序（Heap Sort）
计数排序（Counting Sort）
图解
代码
算法总结与比较
结语
在计算机科学与编程领域，排序算法是基础且核心的知识点之一，它们在数据处理、信息检索、数据分析等多个场景中扮演着至关重要的角色。掌握不同的排序算法不仅能提升解决问题的效率，还能加深对算法原理和时间空间复杂度分析的理解。本文将深入浅出地介绍八大经典排序算法，通过实例解析、算法比较及代码示例，帮助读者全面掌握这些算法的精髓，为日后的开发工作打下坚实的基础。
-
引言
排序的概念
基本概念
- 排序对象：待排序的数据集合，可以是一维数组、列表或其他数据结构中的元素。
- 排序准则：决定元素间先后顺序的规则，通常基于元素的某个属性或键值（如数值大小、字母顺序）。
- 稳定性：如果两个相等的元素在排序前后相对位置不变，则称排序算法是稳定的；反之，则为不稳定。
- 时间复杂度：衡量排序算法执行速度的指标，描述算法执行时间与数据规模的关系，常见的是最好、平均和最坏情况下的时间复杂度。
- 空间复杂度：算法在运行过程中额外占用内存的量，原地排序算法的空间复杂度为O(1)，表示不需要或仅需很小的额外空间。
- 内部排序与外部排序：内部排序指全部数据载入内存完成排序，而外部排序适用于数据量过大无法一次性装入内存的情况，需要借助外部存储进行数据交换。
常见排序算法分类
排序算法依据不同的策略和技术可以分为多种类型，以下是一些经典的排序算法：
- 比较排序：通过比较元素之间的大小关系进行排序，如冒泡排序、选择排序、插入排序、归并排序、快速排序等。
- 非比较排序：不直接比较元素大小，而是利用元素的某种特性（如数学属性）进行排序，如计数排序、基数排序、桶排序等，这类算法通常适用于特定类型的数据集。
- 线性时间排序：在最好和平均情况下具有O(n)时间复杂度的算法，如计数排序、基数排
- 序，但这类算法的适用范围有限。
排序的运用
商品
学校排名
还有很多地方都会用到我们的排序，所以可以看出排序的重要性
-
冒泡排序（Bubble Sort）
-
算法原理与步骤
-
冒泡排序（Bubble Sort）是一种简单的排序算法，其基本原理是通过重复遍历要排序的数列，比较每对相邻元素的值，如果它们的顺序不符合要求（例如，希望升序排序时，前一个元素大于后一个元素），就交换这两个元素的位置。这个过程就像水中的气泡一样，小的元素逐渐“浮”到数列的前端，大的元素则“沉”到数列的末端。下面是冒泡排序的详细步骤：
-
-
动态演示或图解
-
-
-
代码实现（C语言）
-
// 冒泡排序函数
// 参数:
// a: 一个整型指针，指向需要排序的数组
// n: 整型，表示数组中的元素数量
void BubbleSort(int* a, int n) {
// 外层循环控制排序的轮次，共进行n轮比较
for (int i = 0; i < n; i++) {
// 设置一个标记，用于判断本轮循环中是否有元素交换
int flag = 0;
// 内层循环负责每一轮的具体比较和交换操作
// 注意：每轮比较后，最大的元素会被排到最后，所以下一轮可以少比较一个元素
for (int j = 0; j < n - 1 - i; j++) {
// 如果当前元素比下一个元素大，就交换它们的位置
if (a[j] > a[j + 1]) {
Swap(&a[j], &a[j + 1]); // 交换函数，传入两个元素地址进行交换
flag = 1; // 发生了交换，设置flag为1
}
}
// 如果在某一轮遍历中没有发生任何交换，说明数组已经是有序的，可以提前结束排序
if (flag == 0) {
break;
}
}
}
// 辅助函数：交换两个元素的值
// 参数:
// x, y: 整型指针，分别指向需要交换的两个元素
void Swap(int* x, int* y) {
int temp = *x;
*x = *y;
*y = temp;
}-
-
时间复杂度与空间复杂度分析
-
最好情况（已排序）：如果输入数组已经是有序的，冒泡排序只需进行一轮遍历就能发现没有交换发生，此时时间复杂度为O(n)，因为只需要进行一次遍历即可确认数组有序。
最坏情况（逆序或完全无序）：当数组完全逆序或随机无序时，每次遍历几乎都会发生交换，需要进行完整的n*(n-1)/2次比较，此时时间复杂度为O(n^2)。
平均情况：考虑到所有可能的输入情况，平均时间复杂度同样为O(n^2)。这是因为尽管存在最好情况，但在实际应用中很难预先知道数据的排序状态，故平均复杂度反映了一般情况下的性能。
-
适用场景与局限性
这个排序就入门的时候学习一下，因为它好理解，这个排序只有教学意义，比较拉跨，实际开发不用，但是你也要知道有这个排序。
-
选择排序（Selection Sort）
-
原理与实现
-
我写的选择排序做了一点优化，有一点分治的思想吧，从两边向后向前找最大或最小的数，逐渐缩小区间(left <= right)
// 注意检查重叠情况，如果起始位置同时也是最大值的位置，
// 那么在上面的交换后，max位置已经被更新为min的位置，无需再次寻找
if (begain == max) { // 这里实际上逻辑上可以省略，因为下面的交换操作会自动处理这种情况
max = min; // 但为了清晰表达逻辑，这里保留了注释的处理方式
}
这个代码是这种情况：
// 选择排序改进版，同时找出最大和最小值进行交换，适用于偶数长度数组以优化性能
void SelectSort(int* a, int n) {
int begain = 0, end = n - 1; // 初始化起始和结束指针
// 当起始指针小于结束指针时，继续进行排序
while (begain < end) {
int max = begain, min = begain; // 初始化最大值和最小值的索引为起始位置
// 遍历未排序的部分，寻找最大值和最小值
for (int i = begain + 1; i <= end; ++i) {
// 更新最大值索引
if (a[i] > a[max]) {
max = i;
}
// 更新最小值索引
if (a[i] < a[min]) {
min = i;
}
}
// 交换起始位置与最小值
Swap(&a[begain], &a[min]);
// 注意检查重叠情况，如果起始位置同时也是最大值的位置，
// 那么在上面的交换后，max位置已经被更新为min的位置，无需再次寻找
if (begain == max) { // 这里实际上逻辑上可以省略，因为下面的交换操作会自动处理这种情况
max = min; // 但为了清晰表达逻辑，这里保留了注释的处理方式
}
// 交换结束位置与最大值
Swap(&a[end], &a[max]);
// 缩小排序范围
--end; // 移动结束指针向前
++begain; // 移动起始指针向后
}
}-
-
性能分析
-
- 时间复杂度：无论原始数据如何，选择排序都需要进行n-1轮比较，每轮比较都需要遍历剩余未排序的元素，因此时间复杂度为O(n^2)。
- 空间复杂度：选择排序也是原地排序，除了用于交换的少量临时变量外，不需要额外空间，空间复杂度为O(1)。
-
插入排序（Insertion Sort）
-
算法描述
-
看这个图想必大家已经能看懂这个排序
选择排序就是选择一个比他大的值或比他小的值前插入，比如1 3 5我们要把2插入进去，是不是应该插入在1和3之间。
-
-
实现
-
// 插入排序
void InsertSort(int* a, int n) {
// 遍历数组中的每个元素，i从1开始，因为0位置的元素默认已排序
for (int i = 1; i < n; i++) {
int current = a[i]; // 当前需要插入的元素
int j = i - 1; // 已排序部分的最后一个元素的索引
// 将current与已排序部分的元素从后向前比较，如果当前元素小，则将已排序的元素向后移动
while (j >= 0 && a[j] > current) {
a[j + 1] = a[j]; // 向后移动元素
j--;
}
// 将当前元素放到正确的位置
a[j + 1] = current;
}
}-
-
性能
-
时间复杂度
最好情况：当输入数组已经是升序（或降序）排列时，插入排序的性能最优。在这种情况下，每次比较后都不需要移动元素，算法只需进行n-1次比较，时间复杂度为O(n)。
最坏情况：当输入数组是反序时，每次插入都相当于在数组最前面插入新元素，每次插入操作可能需要移动大量的元素。因此，需要进行大约n(n-1)/2次比较和移动，时间复杂度为O(n^2)。
平均情况：对于随机排列的数组，插入排序的平均时间复杂度也是O(n^2)。这是因为尽管某些情况下可以较早停止，但总体上仍然需要进行大量比较和移动操作。
空间复杂度
插入排序是一种原地排序算法，除了几个用于交换和临时存储的变量外，不需要额外的存储空间。因此，其空间复杂度为O(1)，非常节省内存。
-
希尔排序（Shell Sort）
-
分组插入的概念
-
-
-
实现
-
这是第一种写法
// 定义ShellSort函数，用于执行Shell排序算法，传入一个整型数组a和数组长度n
void ShellSort(int* a, int n) {
// 初始化间隔(gap)大小，这里采用常见策略n/3，可根据具体需求调整间隔序列
int gap = n / 3;
// 遍历每个间隔段的起始位置，j从0到gap-1，控制不同的子序列
for (int j = 0; j < gap; j++) {
// 对当前间隔段[j, n-gap)内的每个元素执行插入排序
for (int i = j; i < n - gap; i += gap) {
// 记录待插入元素的索引及值
int end = i;
int tmp = a[end + gap];
// 插入排序逻辑：将tmp插入到已排序的a[end...0]区间中的正确位置
while (end >= 0) {
// 若tmp小于其前面的元素a[end]，则将a[end]后移
if (tmp < a[end]) {
a[end + gap] = a[end];
end -= gap; // 缩小检查范围
}
else {
// tmp不小于a[end]，说明已找到插入位置，跳出循环
break;
}
}
// 将tmp放置到最终确定的位置
a[end + gap] = tmp;
}
}
}简化的写法
/*
定义ShellSort函数，用于执行Shell排序算法，传入一个整型数组a和数组长度n
*/
/*
初始化间隔(gap)大小为数组长度n，随后通过循环不断更新gap值，
采用公式gap = gap / 3 + 1来逐步减小间隔，直至gap <= 1，
这样的间隔序列选择是Shell排序的一种常见策略，旨在平衡效率与简单性
*/
int gap = n;
while (gap > 1) {
// 更新间隔大小
gap = gap / 3 + 1;
// 针对当前的gap值，对数组进行插入排序
for (int j = 0; j < gap; j++) {
for (int i = j; i < n - gap; i += gap) {
// 记录待插入元素的位置及其值
int end = i;
int tmp = a[end + gap];
// 执行插入排序逻辑，将tmp插入到正确位置
while (end >= 0) {
// 若tmp小于其前面的元素，则将前元素后移
if (tmp < a[end]) {
a[end + gap] = a[end];
end -= gap; // 缩小检查范围
}
else {
// 找到tmp的正确插入位置，跳出循环
break;
}
}
// 将tmp放置到最终确定的位置
a[end + gap] = tmp;
}
}
}// 希尔排序函数定义，传入一个整型数组a和数组的元素个数n
void ShellSort(int* a, int n) {
// 初始化间隔(gap)为数组的长度
int gap = n;
// 当间隔大于1时，持续执行以下过程
while (gap > 1) {
// 更新间隔，这里使用gap = gap / 3 + 1的方式递减间隔大小
gap = gap / 3 + 1;
// 遍历数组，步长为当前的gap值
for (int i = 0; i < n - gap; i++) {
// 记录当前位置i及其对应的值tmp
int end = i;
int tmp = a[end + gap];
// 插入排序逻辑：将tmp插入到其应在的正确位置
while (end >= 0) {
// 如果tmp小于其前面的元素，则将前面的元素向后移动
if (tmp < a[end]) {
a[end + gap] = a[end]; // 向后移动元素
end -= gap; // 缩小检查范围
}
else {
// tmp不小于前一个元素，说明找到了插入位置，退出循环
break;
}
}
// 将tmp放到最终确定的位置
a[end + gap] = tmp;
}
}
}注意这里的gap / 3 + 1是特定的写法，你可以计算一下
这边对最后一个写法进行一个动图解释
复杂度分析
最佳情况与平均情况: 对于一些精心设计的间隔序列，例如Hibbard增量序列、Sedgewick增量序列等，希尔排序可以在理论上达到接近O(n log n)的平均时间复杂度。这些序列的设计目的是使得数据在排序过程中迅速趋向有序，从而减少了后续插入排序步骤中的比较和交换次数。
一般情况: 对于常见的间隔序列，比如每次将间隔除以某个常数（如3）加上一个修正值（如1，得到序列如n/3+1, n/9+1, ...），希尔排序的平均时间复杂度大致在O(n log n)到O(n^(3/2))之间。这是由于随着排序的进行，数据的无序程度逐渐降低，但具体的时间复杂度会受到间隔序列选取和数据初始状态的影响。
最坏情况: 在某些不太理想的间隔序列选择下，或者对于特定的输入数据，希尔排序的时间复杂度可能会退化到O(n^2)。这种情况虽然不如快速排序或归并排序稳定，但在实践中，通过合理的间隔序列设计，通常能够避免最坏情况的发生，使得实际表现优于O(n^2)排序算法。
-
归并排序（Merge Sort）
-
分治思想的应用
-
学这个排序之前我们先要看一下这个博客：
数据结构-二叉树-CSDN博客文章浏览阅读1.2k次，点赞28次，收藏28次。数据结构-堆(带图)详解-CSDN博客。https://blog.csdn.net/2302_78381559/article/details/139549132?spm=1001.2014.3001.5502如果你连二叉树是什么？如何实现都不知道的话？抱歉这个排序可能你听不懂。
（递归）看一下最上面的数不是有序的，将它分成两个小组，再将两个小组递归成一个数一个组，是不是每个小组就有序了，（归并）然后我们将小组和小组之间比较，最总就有序了
-
-
递归实现与迭代实现对比
-
递归
注意：我们每个小组排序后，最终也要拷贝一次,因为下一次归并的时候用这个排好序的数据和另一个数据比较，然后再存。
// 归并排序函数，参数包括原始数组a、临时数组tmp、当前子数组的起始索引left和结束索引right
void My_MergeSort(int *a, int *tmp, int left, int right) {
// 基准情况：如果子数组只剩一个元素或为空，则无需排序，直接返回
if (left >= right) {
return;
}
// 计算中间索引，进行分割
int mid = (left + right) / 2;
// 递归地对左右两半进行归并排序
// 左半边: [left, mid-1]
// 右半边: [mid, right]
My_MergeSort(a, tmp, left, mid);
My_MergeSort(a, tmp, mid + 1, right);
// 初始化两个指针数组的起始和结束位置
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
// 初始化临时数组的索引
int i = left;
// 合并过程：当两个子数组都有剩余时比较并放入临时数组tmp
while (begin1 <= end1 && begin2 <= end2) {
// 如果左边数组的当前元素小于右边数组的当前元素
if (a[begin1] < a[begin2]) {
tmp[i++] = a[begin1++]; // 将较小的元素放入tmp，并移动指针
} else {
tmp[i++] = a[begin2++];
}
}
// 处理剩余元素：如果左边数组有剩余，直接复制到tmp
while (begin1 <= end1) {
tmp[i++] = a[begin1++];
}
// 处理剩余元素：如果右边数组有剩余，直接复制到tmp
while (begin2 <= end2) {
tmp[i++] = a[begin2++];
}
// 将tmp中的已排序数据拷贝回原数组a
// 注意：这里拷贝的是[left, right]区间的数据
memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int *a,int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
assert("MergeSort:malloc");
}
My_MergeSort(a,tmp,0,n);
}
非递归
1. 分解（Divide）
将当前区间一分为二，即找到中间位置，然后对两个子区间分别进行排序。这个过程一直递归进行，直到每个子区间只剩下一个元素，这时可以认为单个元素的区间自然就是有序的。
2. 解决（Conquer）
将上一步得到的有序子区间合并成一个大的有序区间。合并的过程是这样的：设立两个指针，最初分别指向两个子区间的起始位置，比较两个指针所指元素的大小，将较小的元素放到结果数组中，并移动对应指针到下一位置，直到某一个子区间的所有元素都被放入结果数组中。然后，将另一个子区间中剩余的元素依次放入结果数组。
3. 合并（Combine）
在递归实现中，每次递归调用返回后，都会进行合并操作，将两个有序子数组合并成一个有序数组。在非递归实现中，通过控制“gap”（步长）逐步扩大排序区间，每轮迭代中对每个“gap”大小的子序列进行合并，直到整个数组变为有序。
非递归版本具体思路：
- 初始化：首先创建一个与原数组相同大小的临时数组
tmp，用于辅助合并排序。- 设定间隔（gap）：初始时，gap设为1，表示只考虑单个元素为一个子序列。随后，每轮迭代将gap翻倍，逐步扩大排序的区间，直到gap大于等于数组长度的一半。
- 多路归并：在每一轮迭代中，对于每个间隔为gap的子序列，将其看作是两个（或一个，如果越界）已排序的子序列，然后进行合并操作。合并过程中，使用双指针技巧比较并移动元素到临时数组
tmp中，最后再拷贝回原数组。- 重复：随着gap的增加，原本小范围有序的子序列会逐渐合并成更大范围的有序序列，直至整个数组排序完成。
- 释放资源：最后，释放临时数组
tmp占用的内存。
// 非递归实现的归并排序函数
void MergeSort_No(int* a, int n) {
// 为临时数组分配内存
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
assert("MergeSort:malloc"); // 内存分配失败时断言
}
int gap = 1; // 初始化间隔大小
// 当间隔小于数组长度时，进行排序
while (gap < n) {
// 对每个子序列进行归并操作
for (int i = 0; i < n; i += 2 * gap) {
// 定义两个子序列的边界
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 打印当前处理的子序列范围，仅用于调试
printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
// 检查第二个子序列是否越界
if (begin2 >= n) {
break; // 越界则跳出本次循环
}
if (end2 >= n) {
end2 = n - 1; // 调整第二个子序列的结束位置以避免越界
}
// 合并两个子序列到tmp数组中
int j = i;
while (begin1 <= end1 && begin2 <= end2) {
if (a[begin1] < a[begin2]) {
tmp[j++] = a[begin1++];
} else {
tmp[j++] = a[begin2++];
}
}
// 复制剩余的元素到tmp中
while (begin1 <= end1) {
tmp[j++] = a[begin1++];
}
while (begin2 <= end2) {
tmp[j++] = a[begin2++];
}
// 将tmp中的有序数据拷贝回原数组a
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); // 拷贝当前处理范围的数据
}
printf("\n"); // 换行，方便观察输出
gap *= 2; // 增大间隔，进行下一轮归并
}
// 释放临时数组的内存
free(tmp);
tmp = NULL;
}-
-
稳定性与效率
-
时间复杂度。归并排序的时间复杂度为O(n log n)，无论是在最好、最坏还是平均情况下，这一复杂度保持不变。这是因为归并排序总是将数组分成两半处理，然后对这两半分别排序，最后合并，这个过程总共需要执行大约n log n次比较和交换操作。即使数据已经是部分有序或者完全无序，归并排序的性能表现都是恒定的。
空间复杂度。归并排序需要额外的存储空间来存放临时数组，用于合并操作，因此其空间复杂度为O(n)。这是归并排序的一个缺点，特别是在处理大量数据时，可能面临较大的内存消耗问题。
-
快速排序（Quick Sort）
-
分区操作详解
-
递归
快速排序基本思想
选取基准值（Pivot）: 在待排序的数组中选择一个元素作为基准值。理想情况下，这个基准值应该能将数组大致分为两个数量相当的部分，从而最大化分治的效果。传统的快速排序随机选择一个元素作为基准，但为了提高效率，可以采用“三数取中法”，即从数组的首元素、尾元素以及中间元素中选择中位数作为基准值，这样做可以在一定程度上避免最坏情况的发生。
分区（Partition）: 将所有比基准值小的元素放置在基准值的左侧，所有比基准值大的元素放置在右侧。这个过程称为分区操作。完成这一步骤后，基准值就位于其最终排序后的位置上。
递归排序子数组: 对基准值左右两侧的子数组分别递归地执行上述两个步骤。递归的终止条件是子数组只剩下一个或没有元素，这时可以认为它们已经排序好了。
“三数取中”策略的引入
为何使用三数取中: 目的是为了避免在数组已经有序或接近有序的情况下，快速排序退化为O(n^2)的最差时间复杂度。通过选择中位数作为基准，可以减少这种极端情况发生的概率，提高算法的平均性能。
如何实施: 在每次递归调用时，先找到数组的第一个元素、最后一个元素和中间元素，然后比较这三个元素的值，将它们中的中位数作为此次排序的基准值。
// 快速排序函数实现
void Quick_Sort(int* a, int left, int right) {
// 基本情况检查：如果待排序区间不足两个元素，则无需排序，直接返回
if (left >= right) {
return;
}
// 对于小数组，使用插入排序以提高效率（这里设定阈值为10）
if ((right - left + 1) < 10) {
InsertSort(a + left, right - left + 1); // 从left位置开始，对长度为right-left+1的子数组进行插入排序
}
else {
// 三数取中：从数组的首元素、中间元素、尾元素中选取中位数作为基准值，以优化快速排序性能
int mid = GetMid(a, left, right); // 获取中位数的索引
Swap(&a[mid], &a[left]); // 将中位数与数组最左侧元素交换，作为基准
// 分区操作：将基准值周围的元素分为两部分，左边都小于基准，右边都大于基准
int begain = left, end = right;
int key = left; // 基准值的索引
// 双指针法进行分区
while (begain < end) {
// 移动end指针，直到找到一个小于基准的元素
while (begain < end && a[key] <= a[end]) {
--end;
}
// 移动begain指针，直到找到一个大于基准的元素
while (begain < end && a[key] >= a[begain]) {
++begain;
}
// 交换找到的不满足条件的元素，使得小的在左边，大的在右边
Swap(&a[begain], &a[end]);
}
// 交换基准值到正确位置
Swap(&a[key], &a[begain]);
key = begain; // 更新基准值的位置
// 对基准值左右两侧的子数组递归进行快速排序
Quick_Sort(a, left, key - 1); // 排序左半部分
Quick_Sort(a, key + 1, right); // 排序右半部分
}
}
// 假设InsertSort和Swap函数已定义
// InsertSort负责对给定范围内的数组进行插入排序
// Swap用于交换两个元素的位置前后指针法
三数取中
/找中间大小值
int GetMid(int* a, int left, int right) {
int mid = (right + left) / 2;
//left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else//left > mid
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}//指针法
// 指针法分区操作
int partsort(int* a, int left, int right) {
// 三数取中选取基准值，提升算法在特定数据分布下的性能
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]); // 将选中的基准值移到数组开头
int prev = left; // 初始化前指针，标记小于基准值区域的末尾
int cur = prev + 1; // 初始化当前指针，遍历数组
int key = left; // 基准值的索引
// 遍历数组，通过交换元素将小于基准值的元素移到数组左侧
while(cur <= right) { // 继续直到当前指针超过右边界
if (a[cur] < a[key]) { // 当前元素小于基准值
if (++prev != cur) { // 防止自我交换
Swap(&a[prev], &a[cur]); // 交换元素
}
}
cur++; // 移动当前指针
}
// 将基准值交换到其最终位置（即小于基准值区域的末尾的下一个位置）
Swap(&a[prev], &a[key]);
return prev; // 返回基准值的最终索引
}
// 快速排序主函数，采用指针法分区
void Quick_Sort_p(int* a, int left, int right) {
// 基础情况判断：如果区间内元素数量小于等于1，则无需排序
if (left >= right) {
return;
}
// 对小数组使用插入排序，减少递归深度和函数调用开销
if ((right - left + 1) < 10) {
InsertSort(a + left, right - left + 1);
} else {
// 调用指针法分区函数获取基准值的最终位置
int key = partsort(a, left, right);
// 递归地对基准值左右两侧的子数组进行排序
Quick_Sort_p(a, left, key - 1); // 排序左半部分
Quick_Sort_p(a, key + 1, right); // 排序右半部分
}
}挖坑法
// 快速排序-挖坑版本
void Quick_Sort_hole(int* a, int left, int right) {
// 基础情况：如果区间内只有一个元素或为空，则无需排序
if (left >= right) {
return;
}
// 三数取中策略选择基准值，减少最坏情况概率
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]); // 将选中的基准值交换到数组开头
int begin = left; // 初始化左指针
int end = right; // 初始化右指针
int hole = left; // 初始化坑的位置，即基准值的初始位置
int key = a[hole]; // 存储基准值
// 双指针法进行挖坑填坑操作
while (begin < end) {
// 从右向左找第一个小于基准值的元素
while (begin < end && key <= a[end]) {
end--;
}
// 找到后，将该元素填入坑中
a[hole] = a[end];
hole = end; // 更新坑的位置
// 从左向右找第一个大于基准值的元素
while (begin < end && key >= a[begin]) {
begin++;
}
// 找到后，再次将该元素填入坑中
a[hole] = a[begin];
hole = begin; // 更新坑的位置
}
// 基准值归位，此时begin == end，即为基准值的最终位置
a[hole] = key;
// 对基准值左右两侧的子数组递归执行快速排序
Quick_Sort_hole(a, left, hole - 1); // 排序左半部分
Quick_Sort_hole(a, hole + 1, right); // 排序右半部分
}快速排序（Quick Sort）- 挖坑版本 的核心思想依然遵循快速排序的基本原则，即分而治之的策略，但它的具体实现细节略有不同，主要体现在如何管理“基准值（pivot）”的选择与定位上。以下是该算法思想的概括：
选择基准值：首先，使用“三数取中”策略选取基准值，即从数组的首元素、中间元素和尾元素中选取中位数作为基准，这样做可以优化在数组已经部分有序的情况下的性能，减少最坏情况发生的概率。
挖坑法：与常规的快速排序直接交换元素不同，挖坑法通过在数组中为基准值“挖一个坑”，然后用符合条件的元素“填坑”。算法维护两个指针，一个从左向右扫描，另一个从右向左扫描，寻找需要交换的元素。当左指针指向的元素大于基准值且右指针指向的元素小于基准值时，交换这两个元素，实际上是将右指针对应的元素“填入”左指针所代表的“坑”中，反之亦然。这一过程不断进行，直至左右指针相遇，此时坑的位置即为基准值的最终位置。
分治：基准值到位后，数组被分为两部分，一部分是所有小于基准值的元素，另一部分是所有大于基准值的元素。然后，对这两部分分别递归地应用同样的挖坑法进行排序。递归的终止条件是子数组的左右边界相遇或交叉，这时子数组只有一个或零个元素，自然有序。
效率与稳定性：挖坑法的快速排序在每次迭代中减少了不必要的元素交换，有时可以略微提高排序效率，尤其是在交换操作成本较高的环境下。然而，快速排序算法整体上是不稳定的排序算法，因为相等的元素可能会因为排序过程中的交换而改变它们的原始相对位置。
非递归
非递归需要用到栈
数据结构-栈(带图)-CSDN博客文章浏览阅读857次，点赞54次，收藏42次。栈（Stack）是一种基本的数据结构，其特点是只允许在同一端进行插入和删除操作，这一端被称为栈顶。遵循后进先出（Last In, First Out, LIFO）原则，即最后存入栈中的元素最先被取出。形象地讲，栈就像是生活中堆放盘子的架子，我们总是把新的盘子放在最上面，而需要拿盘子时也是从最上面开始拿。https://blog.csdn.net/2302_78381559/article/details/138810121
其实非递归也是一种分治的思想，看图
左边入栈出栈完毕之后，出7 5 的时候就对右边排序，这边主要也要看一下partsort函数也就是上面的指针法
//快速排序(非递归)
void Quick_Sort_No(int* a, int left, int right) {
Stack s1;
StackInit(&s1);
//入栈区间
StackPush(&s1, right);
StackPush(&s1, left);
while (!StackEmpty(&s1))//直到栈为空循环结束
{
int begin = StackTop(&s1);
StackPop(&s1);
int end = StackTop(&s1);
StackPop(&s1);
int key = partsort(a, begin, end);//走一次排序，找到key(分治思想)
//[begin,key-1] key [key+1,end]
if (key + 1 < end) {
StackPush(&s1, end);
StackPush(&s1, key+1);
}
if (begin < key - 1)
{
StackPush(&s1, key - 1);
StackPush(&s1,begin);
}
}
StackDestroy(&s1);
}
-
堆排序（Heap Sort）
- 这个排序我专门有一个博客中讲过：
数据结构-堆(带图)详解-CSDN博客文章浏览阅读1.1k次，点赞35次，收藏31次。节点：二叉树的基本组成单位，每个节点可以包含一个数据元素以及指向其左右子节点的引用。根节点：树的顶端节点，没有父节点。叶子节点：没有子节点的节点。度：节点的子节点数量，二叉树中节点的度不超过2。父子关系与兄弟关系：与一般树相同，每个节点（除了根）有唯一的父节点，同一父节点的子节点互为兄弟。https://blog.csdn.net/2302_78381559/article/details/139307800?spm=1001.2014.3001.5502
-
计数排序（Counting Sort）
图解
大概的逻辑就是这样反正通过映射到来排序，这个思想其实有点底层的想法
代码
// 计数排序函数
void Countsort(int* a, int n) {
// 初始化最大值和最小值为数组的第一个元素
int max = a[0], 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*)calloc(range, sizeof(int)); // 分配计数数组内存，初始化为0
if (count == NULL) {
assert("Countsort: calloc failed"); // 内存分配失败时断言
}
// 计数：遍历原数组，统计每个元素的出现次数
for (int i = 0; i < n; i++) {
count[a[i] - min]++; // 将a[i]映射到计数数组的索引，并在此索引上累加计数
}
// 排序：根据计数数组重构原数组
int j = 0; // 用于记录原数组的当前位置
for (int i = 0; i < range; i++) {
// 当前索引i在计数数组中表示的数值是i + min
// 使用计数数组的值进行多次赋值，实现排序
while (count[i]-- > 0) {
a[j++] = i + min; // 将数值i + min放回原数组中，同时移动原数组的写入指针
}
}
// 释放计数数组分配的内存
free(count);
}注意：
- 计数排序适用于整数排序，且数据范围不能太大，否则计数数组将占用大量内存。
- 只针对对整数
- 对于非整数或者数据范围极大的情况，计数排序可能不是最佳选择。
- 计数排序是稳定的排序算法，即相等的元素的相对顺序不会改变。
-
算法总结与比较
源代码
fun.h
#pragma once
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<assert.h>
//接口
// 测试排序速度
void TestOP();
//输出
void My_Print(int* p, int n);
//插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
//void BubbleSort(int* a, int n);
//快速排序
//hoare版
void Quick_Sort(int* a, int left, int right);
//填坑法
void Quick_Sort_hole(int* a, int left, int right);
//指针法
void Quick_Sort_p(int* a, int left, int right);
//非递归
void Quick_Sort_No(int* a, int left, int right);
//归并排序
void MergeSort(int* a, int n);
//归并排序(非递归)
void MergeSort_No(int* a, int n);
//计数排序
void Countsort(int* a, int n);text.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"fun.h"
int main() {
//int arr[] = { 5,6,8,7,1,0,4,9 };
int arr[] = {5,2,3,4,6,9,8 ,10,20,55,11};
int sz = sizeof(arr) / sizeof(arr[0]);
//TestOP();
//InsertSort(arr, sz);
/*BubbleSort(arr, sz);
My_Print(arr, sz);*/
/*HeapSort(arr,sz);
My_Print(arr, sz);*/
/*ShellSort(arr,sz);
My_Print(arr, sz);*/
//My_Print(arr, sz);
//SelectSort(arr, sz);
//My_Print(arr, sz);
//TestOP();
//Quick_Sort_hole(arr, 0, sz - 1);
/*Quick_Sort(arr,0,sz-1);
My_Print(arr, sz);*/
//Quick_Sort_p(arr, 0, sz - 1);
//Quick_Sort_No(arr, 0, sz - 1);
//MergeSort_No(arr,sz);
//My_Print(arr,sz);
Countsort(arr, sz);
My_Print(arr, sz);
}fun.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"fun.h"
#include"fun2.h"
//交换函数
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//打印
void My_Print(int* p, int n) {
for (int i = 0; i < n; i++)
{
printf("%d ", p[i]);
}
printf("\n");
}
//比较时间长
void TestOP() {
// 时间戳+开空间
srand((unsigned int)time(0));
const int n = 100000;
int* a1 = (int*)malloc(sizeof(int) * n);
int* a2 = (int*)malloc(sizeof(int) * n);
int* a3 = (int*)malloc(sizeof(int) * n);
int* a4 = (int*)malloc(sizeof(int) * n);
int* a5 = (int*)malloc(sizeof(int) * n);
// 在每一个下标生成随机数
for (int i = 0; i < n; ++i) {
a1[i] = rand()+i;
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
}
int begin1 = clock();
//InsertSort(a1, n);
int end1 = clock();
int begin2 = clock();
// ShellSort(a2, n);
int end2 = clock();
int begin3 = clock();
// //SelectSort(a3, n);
Quick_Sort_hole(a3, 0, n - 1);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, n);
int end4 = clock();
int begin5 = clock();
Quick_Sort(a5,0,n-1);
int end5 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("Quick_Sort_hole:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("Quick_Sort:%d\n", end5 - begin5);
// // 释放
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
}
// 插入排序
void InsertSort(int* a, int n) {
//[0,end]
for (int i = 0; i < n - 1; i++)
{
int end = i;
//存储目标
int tmp = a[end + 1];
while (end >= 0)
{
//如果end这个位置的值大于tmp就向后覆盖
if (a[end] > tmp) {
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
// 希尔排序
void ShellSort(int* a, int n) {
//预排序
/*int gap = n/3;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end]) {
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}*/
/* int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end]) {
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}*/
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++){
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end]) {
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
// 选择排序
void SelectSort(int* a, int n) {
int begain = 0 ,end = n - 1;
while (begain < end)
{
int max = begain, min = begain;
for (int i = begain+1; i <= end; ++i)
{
if (a[i] > a[max]) {
max = i;
}
if (a[i]< a[min])
{
min = i;
}
}
Swap(&a[begain],&a[min]);
//重叠
//如果begin == max -> begin这个位置就是最大的数，这个数被min的位置换走了，所以只需要将min的下标赋值
if (begain == max) {
max = min;
}
Swap(&a[end], &a[max]);
--end;
++begain;
}
//标准
/* for (int i = 0; i < n-1; i++)
{
int tmp = i;
for (int j = i+1; j < n-1; j++)
{
if (a[tmp] > a[j])
tmp = j;
}
Swap(&a[i], &a[tmp]);
}*/
}
// 堆排序
void AdjustDwon(int* a, int n, int parent) {
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
++child;
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n) {
//建堆(大堆)
for (int i = n/2-1; i > 0 ; i--)
{
AdjustDwon(a,n,i);
}
//排序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
end--;
}
}
// 冒泡排序
//void BubbleSort(int* a, int n) {
//
// for (int i = 0; i < n; i++)
// {
// int flag = 0;
// for (int j = 0; j < n - 1 - i; j++) {
//
// if (a[j] > a[j + 1])
// {
// Swap(&a[j], &a[j + 1]);
// flag = 1;
// }
//
// }
// if (flag == 0)
// {
// break;
// }
// }
//}
//找中间大小值
int GetMid(int* a, int left, int right) {
int mid = (right + left) / 2;
//left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if(a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else//left > mid
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//快速排序
void Quick_Sort(int* a, int left,int right) {
//判断左右等于空，或者左右就一个值
if (left >= right)
{
return;
}
if ((right-left+1) < 10) {
InsertSort(a+left, right - left + 1);
}
else
{
//三数取中
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]);//和左值交换
int begain = left, end = right;
int key = left;
//两边比较(分治思想)
while (begain < end)
{
while (begain < end && a[key] <= a[end])
{
--end;
}
while (begain < end && a[key] >= a[begain])
{
++begain;
}
//交换
Swap(&a[begain], &a[end]);
}
//交换key,和相遇的值
Swap(&a[key], &a[begain]);
key = begain;
//进行递归
//[begain,key-1]key[key+1,end]
Quick_Sort(a, left, key - 1);
Quick_Sort(a, key + 1, right);
}
}
//快排(挖hole版本)
void Quick_Sort_hole(int* a, int left, int right) {
if (left >= right)
{
return;
}
//三数取中
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]);//和左值交换
int begin = left, end = right;
int hole = left;//坑从最左边开始
int key = a[hole];//存储坑的值
while (begin < end) {
while (begin < end && key <= a[end]) {
end--;
}
//填坑
a[hole] = a[end];
//更新坑位
hole = end;
//--------------------
while (begin < end && key >= a[begin]) {
begin++;
}
//填坑
a[hole] = a[begin];
//更新坑位
hole = begin;
}
a[hole] = key;//最后坑位填充存储的值
//递归左右
Quick_Sort_hole(a, left, hole - 1);
Quick_Sort_hole(a, hole+1, right);
}
//指针法
int partsort(int* a, int left, int right) {
//三数取中
int mid = GetMid(a, left, right);
Swap(&a[mid],&a[left]);
int prev = left;
int cur = prev + 1;
int key = left;
//利用循环找key
while(cur <= right)//cur指针大于right边界，跳出循环
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[key]);
return prev;
}
void Quick_Sort_p(int* a, int left, int right) {
//判断左右等于空，或者左右就一个值
if (left >= right)
{
return;
}
if ((right - left + 1) < 10) {
InsertSort(a + left, right - left + 1);
}
else
{
int key = partsort(a,left,right);
//进行递归
//[begain,key-1]key[key+1,end]
Quick_Sort(a, left, key - 1);
Quick_Sort(a, key + 1, right);
}
}
//快速排序(非递归)
void Quick_Sort_No(int* a, int left, int right) {
Stack s1;
StackInit(&s1);
//入栈区间
StackPush(&s1, right);
StackPush(&s1, left);
while (!StackEmpty(&s1))//直到栈为空循环结束
{
int begin = StackTop(&s1);
StackPop(&s1);
int end = StackTop(&s1);
StackPop(&s1);
int key = partsort(a, begin, end);//走一次排序，找到key(分治思想)
//[begin,key-1] key [key+1,end]
if (key + 1 < end) {
StackPush(&s1, end);
StackPush(&s1, key+1);
}
if (begin < key - 1)
{
StackPush(&s1, key - 1);
StackPush(&s1,begin);
}
}
StackDestroy(&s1);
}
#include<string.h>
//归并排序(递归)
//思路：分治思想
void My_MergeSort(int *a,int *tmp,int left,int right) {
if (left >= right)
{
return;
}
//二分数据
int mid = (left + right) / 2;
//[left,mid-1][mid,right] -- 分治
My_MergeSort(a, tmp,left,mid);
My_MergeSort(a, tmp,mid+1,right);
//存储两边
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
//归并
while (begin1 <= end1 && begin2 <= end2)
{
//如果...
if (a[begin1] < a[begin2]) {
tmp[i++] = a[begin1++];//下标不断变化
}
else
{
tmp[i++] = a[begin2++];
}
}
//剩余数据
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));//没归并一次拷贝一次
}
void MergeSort(int *a,int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
assert("MergeSort:malloc");
}
My_MergeSort(a,tmp,0,n);
}
//归并排序(非递归)
void MergeSort_No(int* a, int n) {
//开辟一个临时空间
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
assert("MergeSort:malloc");
}
int gap = 1;//定义gap确定间隔
while (gap < n)
{
//单趟
for (int i = 0; i < n; i += 2 * gap) {
//分治[begin,i+gap-1][i+gap,i+(gap*2)-1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//测试
printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
//判断越界
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
//比较两个区间
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2]) {
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
//将剩余的数也进入
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
//边归并边拷贝(其实可以想一下为什么这样，每拷贝一次a都会变化，这样才能真正的排序)
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//(end2-i)+1 == 这是最后一个位置+1，下标从0开始
}
printf("\n");
gap *= 2;
}
//销毁
free(tmp);
tmp = NULL;
}
//计数排序
void Countsort(int* a,int n) {
//找最大值/最小值
int max = a[0], 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*)calloc(range, sizeof(int));
if (count == NULL)
{
assert("Countsort:calloc");
}
for (int i = 0; i < n; i++)
{
count[a[i] - min]++; // a中的数字减去最小值，就可以的到这个数字顺序的下标
}
//排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--) {
a[j++]= i + min;//用i + min就的到原来的数字，将这些存入a数组
}
}
//释放
free(count);
}结语
深入探讨了八大排序算法——冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、以及我们刚刚详析的计数排序之后，我们不仅掌握了一系列解决排序问题的有效策略，更深刻理解了算法设计背后的逻辑与权衡。每种算法，如同八音盒中的音符，各有其独特的旋律与应用场景，它们共同编织了计算机科学领域中关于“排序”这一基本问题的华丽乐章。
