目录
1.排序的概念
2.插入排序
2.1直接插入排序
2.1.1核心思想及代码实现
2.1.2复杂度和稳定性
2.2折半插入排序
2.2.1核心思想及代码实现
2.2.2复杂度和稳定性
2.3希尔排序
2.3.1核心思想及代码展示
2.3.2缩小增量方案
2.3.3复杂度和稳定性
3.选择排序
3.1简单选择排序
3.1.1核心思路及代码实现
3.1.2复杂度和稳定性
3.2堆排序
3.2.1核心思想及代码实现
3.2.2复杂度和稳定性
4.交换排序
4.1冒泡排序
4.1.1核心思路及代码实现
4.1.2复杂度和稳定性
4.2快速排序
4.2.1核心思想及代码实现
4.2.2复杂度和稳定性
5.归并排序
5.1核心思想及代码实现
5.2复杂度和稳定性
6.计数排序
6.1核心思想及代码实现
6.2复杂度和稳定性
1.排序的概念
排序（Sorting），顾名思义，就是将一组杂乱无章的“数据”（记录），按照某个特定的“关键字”（Key），重新排列成一个有序序列的过程。
1.1 排序算法的评价指标
- 时空复杂度
- 稳定性：相同值的元素，排序后相对顺序是否保持不变。
1.2内部排序和外部排序
- 内部排序：所有数据都能加载到内存中完成排序。内部排序关注如何让复杂度更低。
- 外部排序：数据量巨大（如几十TB），无法全部装入内存，必须借助磁盘文件和多路归并分批次排序。外部排序关注如何使读写硬盘的次数更少。
1.3排序过程动图网站
- Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo
- Comparison Sorting Visualization
2.插入排序
2.1直接插入排序
2.1.1核心思想及代码实现
将数组逻辑上分为两个区间：左侧是有序区（初始只有一个元素），右侧是无序区（剩下的元素）。
每轮循环：
- 抓牌：从无序区取出第一个元素(key)
- 挪位：在有序区从后往前扫描，把比key大的值往后移动一位
- 插入：当遇到第一个比key小或相等的元素时，停止移动，将key插入到这个元素后面的空位上
代码实现：
void InserSort(int* a, int n) { // 外层循环：控制有序区间的范围 // i 表示当前有序区间的最后一个元素下标，初始时有序区间只有 a[0]（即 i=0） // 循环条件 i < n-1，确保要取出的 key = a[end + 1] 不会越界 for (int i = 0;i < n - 1;i++) { int end = i; int key = a[end + 1]; // 内层循环：在有序区 [0, end] 中从后往前扫描 while (end >= 0) { if (key < a[end])// 写成 key<=a[end] 会影响稳定性 { a[end + 1] = a[end]; end--; } else { // 如果 key >= a[end]，说明找到了插入位置 break; } } // 1. 如果是 break 退出：end 指向最后一个 <= key 的元素，key 插入到 end+1 // 2. 如果是 end == -1 退出（key 比所有元素都小），插入到最前面；所以这句代码不可以放到else里 a[end + 1] = key; }注意：
1.if (key<a[end])//这句写成if (key<=a[end])会影响稳定性
2.a[end + 1] = key;//这句代码不能写在else里，否则当key 比所有元素都小时，该句不执行
2.1.2复杂度和稳定性
时间复杂度：
- 最坏情况：逆序，如：要排升序，序列本身为降序，时间复杂度为O(n^2)
- 最好情况：正序，如：要排升序，序列本身为升序，则时间复杂度为O(n)
- 平均情况：O(n^2)
空间复杂度：O(1)
总结：直接插入排序看序列的原始顺序，当序列有序或接近有序时，效率较高
稳定性：稳定
2.2折半插入排序
2.2.1核心思想及代码实现
利用“已排序区间是有序的”这一特性，将查找插入位置的过程从顺序查找改为折半查找（二分查找），从而减少了比较次数。
代码实现：
#include <stdio.h> // 折半插入排序（升序，稳定） void binaryInsertionSort(int arr[], int n) { int i, j, left, right, mid, temp, pos; for (i = 1; i < n; i++) { temp = arr[i]; // 取出待插入元素 left = 0; right = i - 1; // 已排序区间的左右边界 // 1. 二分查找插入位置（严格大于，保证稳定性） while (left <= right) { mid = (left + right) / 2; if (arr[mid] > temp) { right = mid - 1; // 继续在左半部分找 } else { left = mid + 1; // 相等时向右找，保证稳定 } } pos = left; // 最终插入位置 // 2. 元素后移（从 i-1 到 pos，倒序移动） for (j = i - 1; j >= pos; j--) { arr[j + 1] = arr[j]; } // 3. 插入元素 arr[pos] = temp; } }2.2.2复杂度和稳定性
时间复杂度：折半插入排序减少了比较次数，但移动次数不变，因此总时间复杂度依然是O(n^2)
稳定性：稳定
总结：折半插入排序的优化效果有限
2.3希尔排序
2.3.1核心思想及代码展示
希尔排序是直接插入排序的改进，又称缩小增量排序
预排序（分组）：选定一个增量
gap，将相隔gap个位置的元素归为一组，共分成gap组。组内插入：对每一组分别进行直接插入排序。
缩小增量：将
gap缩小，重复上述分组排序过程。最后冲刺：当
gap = 1时，全体元素视为一组，进行最后一次直接插入排序。此时数组已经基本有序，因此最后一次的移动次数极少。
代码实现：
void ShellSort(int* a, int n) { int gap = n; while (gap > 1)//采用下面的方法缩小增量，这里就不能写 >= 1，否则会死循环 { //1.采用 gap = gap/3 + 1 增量序列 gap = gap / 3 + 1; // 2.外层循环：遍历所有组的起始位置，代表 gap 个不同的分组，gap是几就有几组 for (int j = 0;j <gap;j++) { // 3.内层循环：对当前起始位置为 j 的这一组进行直接插入排序 for (int i = j;i + gap < n;i += gap) { int end = i; int key = a[end + gap]; // 组内向前比较并移动：将 key 插入到已排序的组内正确位置 while (end >= 0) { if (key < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = key; } } } }更简单的写法：
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; // 以下为交替处理所有组的插入排序（等价于分组处理） for (int i = 0;i + gap < n;i++) { int end = i; int key = a[end + gap]; while (end >= 0) { if (key < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = key; } } }2.3.2缩小增量方案
| 方案 | 增量生成公式 | 时间复杂度 | 优缺点 |
| Shell 增量 | gap = gap / 2 | O(n^2) | 缺点： 1.增量序列不互质，在变成 gap=1之前，奇数位置的元素和偶数位置的元素永远被隔离开。 （如果奇数位置全是小数，偶数位置全是大数，那么前几轮预排几乎没有作用） 2.所以最坏时间复杂度依然是O(n^2) |
Knuth 增量 （最常用） | d = d / 3 + 1 | O(n^(3/2)) | 优点： 增量之间互质，跳跃更均匀，预排序效果好； 公式简单，工程实现友好。 |
| Sedgwick 增量 | 9⋅4^i−9⋅2^i+19⋅4^i−9⋅2^i+1 和 4^i−3⋅2^i+1 | 最快 | 缺点：太复杂 |
2.3.3复杂度和稳定性
时间复杂度：如上表
稳定性：不稳定。（由于分组是跳跃式的，相同元素可能被分到不同组中独立排序，无法保证它们的相对顺序。）
3.选择排序
3.1简单选择排序
3.1.1核心思路及代码实现
简单选择排序：每次从待排序的序列中选出最小（或最大）的那个，放到最前面。
将数组分为已排序区（左侧）和未排序区（右侧）。
每一轮从未排序区中找出最小元素的下标。
将该最小元素与未排序区的第一个元素交换位置。
已排序区扩大一位，未排序区缩小一位。
重复此过程，直到所有元素排完。
选择排序和插入排序的区别：
- 插入排序是“拿一张牌插入到已排好的牌堆中”；
- 选择排序是“在剩下的牌堆里翻出最小的那张，直接放到牌堆末尾”。
代码实现：
void SelectSort(int* a, int n) { // 外层循环：控制已排序区的边界 // i 表示未排序区的第一个元素下标，同时也是本轮要放置最小值的位置 // 只需执行 n-1 轮，因为最后一个元素会自动就位 for (int i = 0; i < n - 1; i++) { int min = i; // 假设当前未排序区的第一个元素（下标 i）是最小值 // 内层循环：在未排序区 [i, n-1] 中遍历，找出真正最小值的下标 // j 从 i+1 开始，因为 a[i] 已经作为初始候选 for (int j = i + 1; j < n; j++) { // 如果发现更小的元素，更新 min 为新的下标 if (a[j] < a[min]) { min = j; } } // 如果找到的最小值不是 a[i]（即 min != i），则交换两者 // 如果 min == i，说明 a[i] 本身就是最小值，无需交换，节省操作 if (min != i) { int tmp = a[i]; a[i] = a[min]; a[min] = tmp; } } }3.1.2复杂度和稳定性
时间复杂度：无论数组是否有序，每趟都需要去比较选出最小的数据，比较次数恒为 n(n−1)/2，所以时间复杂度为O(n^2)
稳定性：不稳定。如：5 8 5 2
3.2堆排序
3.2.1核心思想及代码实现
升序建大堆，降序建小堆（这里排升序）
建堆：将待排序数组重新排列，构建成一个大堆。使堆顶元素成为全局最大值。
排序：
将堆顶（最大值）与堆的最后一个元素交换，此时最大值归位。
将堆的大小减 1（排除已归位的最大值），并对新的堆顶执行向下调整，使其重新变成大堆。
重复上述过程，直到堆中只剩 1 个元素，排序完成。
代码实现：
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //向下调整算法 void AdjustDown(int* a,int n,int parent) { int child = parent * 2 + 1; while (child < n)//没有孩子可以比较就结束 { //选出较大的孩子 if (child + 1 < n && a[child] < a[child + 1]) { child++; } if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //堆排序 void HeapSort(int* a, int n) { //排升序，建大堆 for (int i = (n - 1 - 1) / 2;i >= 0;i--) { AdjustDown(a, n, i); } int j = 1; while (n - j > 0) { Swap(&a[0], &a[n - j]); AdjustDown(a, n - j, 0); j++; } }3.2.2复杂度和稳定性
时间复杂度：O(nlogn)
稳定性：不稳定。堆排序的交换是跳跃式的（比如堆顶和堆尾交换），可能跨越很长的距离，打乱相同元素的相对顺序。
4.交换排序
4.1冒泡排序
4.1.1核心思路及代码实现
重复遍历数组，依次比较相邻的两个元素，如果顺序错误就交换，直到整个数组有序。
每一趟从数组开头开始，依次比较相邻的两个元素
a[j]和a[j+1]。如果
a[j] > a[j+1]（升序），就交换它们。经过第一趟，最大值一定会“冒泡”到数组的最后一个位置。
下一趟只需要遍历到倒数第二个位置（因为最后一个已经最大了）。
重复
n-1趟，数组就有序了。
代码实现：
void BubbleSort(int* a, int n) { // 1.外层循环：控制排序的趟数 // 每排完一趟，就有一个最大的数沉到末尾，所以最多需要 n-1 趟 // 这里用 i 记录已经排好的元素个数（i 从 0 开始） for (int i = 0; i < n - 1; i++) { int flag = 0; // 2.内层循环：进行相邻元素的两两比较 // 因为末尾已经排好了 i 个元素，所以内层只需要比较前 n-i-1 个 for (int j = 0; j < n - i - 1; j++) { // 使用 > 而不是 >=，保证了稳定性（相等的元素不会交换位置） if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; flag = 1; } } // 3. 若没有发生交换，说明已经有序 if (flag == 0) break; } }4.1.2复杂度和稳定性
时间复杂度：
- 最坏：逆序序列，比较次数为1到n-1的等差数列，O(n^2)
- 最好：正序序列，比较n-1次，没有发生交换，时间复杂度为O(n)
稳定性：
if (a[j]>a[j + 1]); // 使用>而不是>=时，是稳定的（相等的元素不会交换位置）
4.2快速排序
4.2.1核心思想及代码实现
采用分治思想：在待排序任选一个元素作为基准值，基准值左边比它小，右边比它大（升序）；然后对左右两边分别递归地重复这个过程，直到子区间不能再划分。
选基准（Key）：从待排序区间中选出一个元素作为“基准值”（pivot）。
分区（Partition）：将区间内的元素重新排列，使得所有比基准小的元素都在基准左边，所有比基准大的元素都在基准右边。此时，基准元素就已经归位了（它就在最终排序后的正确位置上）。
递归分治：对基准左边和右边的两个子区间，分别递归地重复第1、2步，直到子区间只剩一个元素，整个数组就有序了。
找基准值及分区：
1. 挖坑法
- 挖坑：将最左侧元素取出来，作为基准值 pivot。此时，这个位置就变成了一个“空坑”
- 填左坑：从右向左找小，找到比 pivot 小的元素，放到左边的坑里，此时右边被挖的位置就形成了新的“空坑”。
- 填右坑：从左向右找大，找到比 pivot 大的元素，放到右边的坑里，此时左边被挖的位置就形成了新的“空坑”。
- 重复：左右指针不断向中间移动，交替“挖坑-填坑”。
- 填回基准：当左右指针相遇（left == right），此时，这个位置就是基准值的位置，将其填入
int PartitionDigHole(int* a, int left, int right) { // 1. 挖坑：把最左边的元素挖出来 int pivot = a[left]; // 2. 循环条件：左右指针未相遇 while (left < right) { // 3. 从右向左找小（填左边的坑） while (left < right && a[right] >= pivot) { right--; } a[left] = a[right]; // 4. 从左向右找大（填右边的坑） while (left < right && a[left] <= pivot) { left++; } a[right] = a[left]; } // 5. 左右指针相遇（left == right），把 pivot 放入最后的坑 a[left] = pivot; // 返回基准值归位的下标 return left; }2. Lomuto法
- 基准值：假设选最右边的元素为基准值 pivot。
- prev：指向小于基准值的最后一个元素。一开始指向区间最左侧的前一位,（即 left-1）
- cur：从最左边开始，向右找比基准值小的值，与 prev 的下一个元素交换。
- 终止：当 cur 遍历到基准值的前一个位置（即 right - 1）时循环停止。此时，prev 指向最后一个小于 pivot 的元素。
- 归位：最后，将基准值交换到 prev 的下一个位置，基准值完成归位。
int PartitionLomuto(int* a, int left, int right) { // 1. pivoti 记录基准值的下标 // 2. cur 指向当前正在扫描的元素 // 3. prev 指向 "小于基准区域的最后一个元素" int pivoti = right; int cur = left; int prev = left - 1; // 4. 循环遍历区间 [left, right-1] while (cur < right) { //后面这句：防止自己和自己交换 if (a[cur] < a[pivoti] && ++prev != cur) { int tmp = a[cur]; a[cur] = a[prev]; a[prev] = tmp; } cur++; } // 5. 循环结束：将基准值（a[pivoti]）交换到 prev + 1 位置 int tmp = a[pivoti]; a[pivoti] = a[++prev]; a[prev] = tmp; return prev; }
代码实现：
void QuickSort(int* a, int left, int right) { // 当左边界 >= 右边界时，说明当前区间无效或只有一个元素 // 情况1：left == right，区间内只有1个元素，天然有序，直接返回 // 情况2：left > right，区间为空（比如基准在左边界时，左子区间为空），直接返回 if (left >= right) return; // 调用分区函数 // 作用：选取基准值，并将区间内元素重新排列，使得： // 1. a[pivotkeyi] 已经是最终排序后的正确元素（基准归位） // 2. [left, pivotkeyi-1] 范围内的所有元素都 <= 基准值 // 3. [pivotkeyi+1, right] 范围内的所有元素都 >= 基准值 // 返回值：基准值最终归位的数组下标（即分界点） int pivotkeyi = PartitionDigHole(a, left, right); //int pivotkeyi = PartitionLomuto(a, left, right); //递归排序左右子区间 QuickSort(a, left, pivotkeyi - 1); QuickSort(a, pivotkeyi + 1, right); }
- 每轮排序的核心是先通过分区操作使基准值归位（确定其最终下标），将当前区间拆分为左右两个子区间；
- 然后递归地对这两个子区间反复执行相同的归位操作，层层缩小待排序范围，直至所有子区间都不可再分（元素个数为 0 或 1）。
- 当所有子区间均递归有序时，整个数组就有序了。
总结：快速排序本质上就是逐个让基准值归位的过程。
4.2.2复杂度和稳定性
时间复杂度：
- 最坏时间复杂度：快排效率取决于基准值的选取，如果每次选的基准都是最大或最小值，快排的效率达到最坏，时间复杂度为O(n^2)
- 平均时间复杂度：O(nlogn)
空间复杂度：O(logn)递归调用栈的深度，对应二叉树的高度
稳定性：不稳定 。分区过程中存在跨距离交换。比如 1 1 1 1
5.归并排序
5.1核心思想及代码实现
归并排序是将两个或两个以上的有序表 合成一个新的有序表的过程。
链表可以尾插归并，数组则要开辟辅助数组进行排序。
- 分解：将待排序数组从中间一分为二，分成左右两个子数组。
- 解决：递归地对左右两个子数组分别进行归并排序，直到子数组长度为 1（天然有序）。
- 合并：将两个已经有序的子数组合并成一个更大的有序数组，需要借助额外的辅助数组。
- 注意：写代码时注意控制细节
与快排的区别：
快排的划分是按“值”（基准左边小、右边大）；归并的划分是按“位置”（直接取中间下标）。
快排在“合并”阶段啥都不用干（原地归位）；归并在“合并”阶段需要干大量的搬移工作。
代码实现
// 归并排序的子函数 // begin 当前区间左边界（闭区间） // end 当前区间右边界（闭区间） void _Merge(int* a, int begin, int end, int* tmp) { // 1.当区间内没有元素或只剩一个元素时，天然有序，直接返回 if (begin >= end) return; // 2.分解 int mid = (begin + end) / 2; // 将当前区间分为[ begin, mid],[ mid+1, end] // 不能划分为 [begin, mid - 1],[mid, end] ，否则会死循环 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; // 3.解决 // 注意：这里必须先递归排完左右两边，再执行合并。 // 只有左右子区间内部都有序了，下面的二路归并才有意义。 _Merge(a, begin1, end1, tmp); _Merge(a, begin2, end2, tmp); // 4.归并 // 此时，左子区间[begin1, end1] 和右子区间[begin2, end2] 已各自有序 // 要将这两个有序数组合并成一个大的有序数组，暂存到 tmp 中 int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) // <= 保证稳定性 { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } // 如果左右子区间还有剩余元素，全部拷贝到 tmp 后面 while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } // 5.拷贝到原数组 for (int j = begin; j <= end; j++) { a[j] = tmp[j]; } } void MergeSort(int* a, int n) { // 申请辅助空间 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc"); return; } // 调用递归子函数，从整个数组区间 [0, n-1] 开始归并 _Merge(a, 0, n - 1, tmp); // 别忘了释放 free(tmp); tmp = NULL; }5.2复杂度和稳定性
- 时间复杂度：O(nlogn),无论数组是否有序，递归树高度永远是 logn，每层合并总耗时都是 O(n)。
- 空间复杂度：O(n),需要额外的临时数组 tmp 来存放合并结果。
- 稳定性：让前半区间的值先归并可以保证稳定性。(if (a[begin1]<=a[begin2]) //<=保证稳定性)
6.计数排序
6.1核心思想及代码实现
计数排序利用数组下标来定位置，而不是通过比较来决定顺序。
使用前提：
- 数据跨度不能太大
- 数据必须为整数
思路：
需要用到3个数组，原数组 a，计数数组 count，辅助数组 tmp
- 统计：遍历原始数组，以“当前元素值减去最小值”作为索引，在计数数组count的对应位置上进行自增操作，记录每个不同元素值出现的总次数。
- 累加：从计数数组的第一个元素开始，依次执行累加操作。此时，count[ i ] 的含义不再代表频次，而是代表原始数组中，所有小于等于当前值的元素个数。
- 反向填充：逆序遍历原数组（从最后一个元素开始向前遍历）。采用逆序填放，是为了保证当遇到重复元素时，原数组中靠后的元素仍然放置在输出数组靠后的位置，从而维持算法的稳定性。
代码实现：
void CountSort(int* a, int n) { // 防止传入空指针或长度为0的数组，避免后续访问越界 if (n <= 0) return; // 1.找出数据的极值（确定范围） // 初始化 min 和 max 为第一个元素 int i = 0; int min = a[i], max = a[i]; // 遍历整个数组，找出实际的最小值和最大值 for (i = 1; i < n; i++) { if (min > a[i]) min = a[i]; if (max < a[i]) max = a[i]; } // 2.开辟计数数组 // 计算数值跨度（闭区间元素个数），例如 [10, 19] 的 range = 19-10+1 = 10 int range = max - min + 1; int* count = (int*)calloc(range, sizeof(int));// calloc 会将所有元素初始化为 0 if (count == NULL) { perror("calloc"); return; } // 3.统计频率 for (i = 0; i < n; i++) { count[a[i] - min]++; // 该位置计数加1 } // 4.开辟辅助数组（用于存放排序结果） int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc"); free(count); return; } // 5.前缀和累加 // 累加后：count[i] 代表 "小于等于该值的元素总个数"（即右边界排位） for (i = 1; i < range; i++) { count[i] += count[i - 1]; } // 6。反向填充（确保稳定性） for (i = n - 1; i >= 0; i--) { // 1. 计算当前值对应的下标 idx = a[i] - min // 2. 获取该值的排位 count[idx]，减1后作为数组下标 // 3. 放置数据，并将 count[idx] 自减1 tmp[count[a[i] - min] - 1] = a[i]; count[a[i] - min]--; } // 7.拷贝回原数组 for (i = 0; i < n; i++) { a[i] = tmp[i]; } free(tmp); tmp = NULL; free(count); count = NULL; }6.2复杂度和稳定性
时间复杂度：假设n是数据个数，range是数据范围，则时间复杂度为O(n+range)，若range接近于n,则时间复杂度为O(n)
空间复杂度：O(n+range)。
稳定性：稳定。因为反向遍历原数组
