引言：本章简洁的讲解一下数据结构中的几个常见的排序 ，作复习之用，后面可能会补一些其他的排序 。并给出一些小编学习中遇到的坑，作借鉴。
1.直接插入排序
直接插入排序是一种简单直观的排序算法，其基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
易写错的地方：
1. 循环边界问题
// 错误：可能导致数组越界 for(i = 0; i < n; i++) // 应改为 i < n-1原因：
当i达到n-1时，end为n-1，此时a[end+1]即a[n]，会访问数组越界。正确写法：
for(i = 0; i < n-1; i++) // 循环到 n-2，确保 end+1 <= n-1
2. 待插入元素保存位置错误
错误写法：
在循环内部错误更新tmp的值。// 错误：每次循环都重新赋值 tmp while(end >= 0) { int tmp = a[end+1]; // 错误：应在循环外保存一次 ... }原因：
tmp应在每次外层循环开始时保存当前待插入的元素，而非在循环内部重复赋值。正确写法：
// 正确：在循环外保存待插入元素 int tmp = a[end+1]; while(end >= 0) { ... }
3. 插入位置错误
错误写法：
插入操作位置错误，导致元素覆盖。// 错误：可能覆盖未处理的元素 a[end] = tmp; // 应改为 a[end+1] = tmp原因：
当while循环结束时，end指向的是第一个小于等于 tmp 的元素，因此tmp应插入到end+1位置a[end+1] = tmp; // 插入到正确位置
【示范代码】
//直接插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//循环边界是 n-1,防止越界
{
//单趟排序
int end = i; //end是数组下标
int tmp = a[end+1]; //tmp是数组元素//保存a[i+1]
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];//向后移位
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;//将tmp放在正确的位置
}
}2.希尔排序
希尔排序（Shell Sort）是插入排序的一种改进版本，也被叫做缩小增量排序。和直接插入排序比起来，它的效率更高，主要是通过将原始数据分成多个子序列来减少元素移动的次数，不过子序列的划分并非简单地逐段分割，而是依据特定的增量来进行。
希尔排序的核心思路是：先将整个待排序的记录序列分割成若干个子序列，分别对这些子序列进行直接插入排序。随着增量逐渐减小，子序列的长度越来越大，整个序列会变得越来越接近有序。当增量减至 1 时，整个序列就会被合并为一个，再进行一次直接插入排序，此时排序完成。
【示范代码】
插入排序 --- 希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
//gap = gap/3+1;
while (gap > 0)
{
gap /= 2;
for (int i = 0; i + gap < n; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end = end - gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
3.选择排序
选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每一轮从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完(同时它也是最烂的排序)
【示范代码】
//选择排序 同时选出大和小 a.
void DSelectSort(int* a, int n)
{
int left = 0, right = n - 1;
while (left < right)
{
int mini = left, maxi = left;
for (int i = left+1; i <= right; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[left], &a[mini]);
if (left == maxi)
{
maxi = mini;
}
Swap(&a[right], &a[maxi]);
left++;
right--;
}
}
//选择排序 -- 只选出小的进行交换 b.
void SSelectSort(int* a, int n)
{
int left = 0;
while(left < n)
{
int min = left;
for (int i = left; i < n; i++)
{
if (a[min] > a[i])
{
min = i;
}
}
Swap(&a[left], &a[min]);
left++;
}
}
4.堆排序
堆排序（Heap Sort）是一种基于二叉堆数据结构的高效排序算法，它利用堆的特性进行排序，时间复杂度为 O (n log n)，且是一种原地排序算法（空间复杂度 O (1)）。
易写错的地方：
- AdjustDown 函数中的条件判断
在AdjustDown函数里，要判断右孩子是否存在，同时还要比较左右孩子的大小。要是这一步没处理好，可能会造成数组越界。if (child + 1 < n && a[child] < a[child + 1])
- 建堆的起始位置
建堆得从最后一个非叶子节点开始，也就是(n-1-1)/2。要是起始位置搞错了，堆的性质就无法保证。for (int i = (n - 1 - 1) / 2; i >= 0; --i)
- 交换元素和调整范围
在排序阶段，每次把堆顶元素和当前未排序部分的末尾元素交换之后，要对剩余元素重新进行调整。此时，调整范围会逐步减小。Swap(&a[end], &a[0]); AdjustDown(a, end, 0); // 注意这里是end，而不是n
【示范代码】
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[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 - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a,n,i);
}
//向下调整排序
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
end--;
}
}5.冒泡排序
冒泡排序（Bubble Sort）是一种简单直观的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成（具有教学意义）
【示范代码】
// 交换排序
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n - j - 1; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
}
}
}
}6.快速排序
快速排序（QuickSort）是一种基于分治（Divide and Conquer）策略的排序算法，由托尼・霍尔（Tony Hoare）于 1959 年提出。它通过选择一个 “基准值”（Pivot），将数组分成两部分，一部分的元素都比基准值小，另一部分都比基准值大，然后递归地对这两部分进行排序，最终实现整个数组有序。
6.1 快速排序的简单写法
//快速排序 -- 递归 最简单的一种写法
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int end = right, begin = left;
//单趟排序
int keyi = left;
while (left < right)
{
//右边先走 找小
while(left < right && a[right] >= a[keyi])
{
right--;
}
//找大
while(left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
//递归循环
QuickSort(a, begin,keyi-1);
QuickSort(a, keyi+1,end);
}6.2 优化取值
6.21优化方式 1 -- 三数取中
1.什么是三数取中？ 2.为什么要三数取中？
1.1 三数取中（Median of Three）是快速排序的一种优化策略，核心思想是在当前排序区间中选取左端、右端、中间位置的三个元素，比较它们的值后选择中间值作为基准值（Pivot）。
例如，对于数组区间arr[low...high]，计算中间位置mid = low + (high - low) / 2，比较arr[low]、arr[mid]、arr[high]，将中间值与区间左端（或右端）元素交换，使基准值位于区间边界，再进行常规的快速排序分区操作。
2.1避免最坏情况
传统快速排序若直接选择固定端点（如左端）作为基准值，在数组已排序或接近排序时会退化为最坏时间复杂度O(n²)（每次分区极度不平衡）。
三数取中能显著降低基准值为极值的概率，使分区更平衡，平均时间复杂度趋近于理想的O(n log n)。
2.2. 减少极端数据影响
对于存在大量重复元素或有序性较强的数组，三数取中可有效避免基准值偏向某一端，提升算法稳定性。
2.3. 实现简单高效
仅需额外 3 次元素比较和 1 次交换操作，代价极低，却能大幅优化基准值的选择
6.22 优化方式2 -- 随机取值
随机取值（Random Pivot）是另一种基准值优化策略，具体做法是在当前排序区间内随机选择一个元素作为基准值，通常通过生成随机索引（如randomIndex = low + rand() % (high - low + 1)）实现。
6.3 三种快速排序的三种优化的方法（三数取中）
a.hoare 霍尔
//a.霍尔//hoare
int Part1(int* a, int left, int right)
{
int midi = GetMidNumi( a, left, right);
if (midi != left)
{
Swap(&a[midi], &a[left]);
}
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while(left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
return keyi;
}b.挖坑法
//b.挖坑法
int Part2(int* a, int left, int right)
{
int midi = GetMidNumi( a, left, right);
if (midi != left)
{
Swap(&a[midi], &a[left]);
}
int key = a[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;
return hole;
}c. 前后指针
//c.前后指针法
int Part3(int* a, int left, int right) {
int midi = GetMidNumi(a, left, right);
if (midi != left)
{
Swap(&a[midi], &a[left]);
}
int keyi = left;
int slow = left;
int fast = left + 1;
while (fast <= right)
{
if(a[fast] < a[keyi] && ++slow!= fast)
{
Swap(&a[fast], &a[slow]);
}
fast++;
}
Swap(&a[slow], &a[keyi]);
keyi = slow;
return keyi;
}void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
//int keyi = Part1(a, left, right);
//int keyi = Part2(a, left, right);
int keyi = Part3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}7.归并排序
归并排序（Merge Sort）是一种基于分治思想的高效排序算法，由约翰・冯・诺伊曼（John von Neumann）于 1945 年提出。它将数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。
【示范代码】
//归并排序
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
// 1. 递归终止条件
if (begin >= end)
return;
// 2. 分割数组
int mid = (begin + end) / 2;
// [begin, mid] [mid+1,end]，子区间递归排序
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
// 3. 合并两个已排序子数组
// [begin, mid] [mid+1,end]归并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
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++];
}
// 4. 将临时数组结果复制回原数组
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}