引言：本章简洁的讲解一下数据结构中的几个常见的排序 ，作复习之用，后面可能会补一些其他的排序 。并给出一些小编学习中遇到的坑，作借鉴。
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));
}
