排序算法全解析：插入、希尔、选择、堆、冒泡、快排、归并与计数排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
// 贯穿全文的测试数组
int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
int n = sizeof(a) / sizeof(a[0]);   // n = 9
 
// 交换两个整数的工具函数，后面所有排序都会用到
void swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

// 直接插入排序：把第 i 个元素插入到前面 i-1 个已有序的元素中
void InsertSort(int* a, int n)
{
    // i 表示当前待插入元素的前一个位置，i 从 0 到 n-2
    // 第 i 轮把 a[i+1] 插入到 [0, i] 这个有序区间中
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;            // end 指向已有序区间的最后一个位置
        int tmp = a[end + 1];   // tmp 保存待插入的元素
        // 从后往前比较：只要前面的元素比 tmp 大，就往后挪一位
        while (end >= 0)
        {
            if (a[end] > tmp)
            {
                a[end + 1] = a[end];  // 大元素后移，腾出位置
                end--;
            }
            else
            {
                break;   // 找到合适位置，跳出
            }
        }
        a[end + 1] = tmp;   // 把 tmp 放进找到的位置
    }
}

初始：    5  3  9  6  2  4  7  1  8
 
第1轮 i=0：tmp = 3
  5 > 3 → 5 后移        → [_, 5] 9 6 2 4 7 1 8
  3 放入位置0           → [3, 5] 9 6 2 4 7 1 8
 
第2轮 i=1：tmp = 9
  5 > 9 ? 否，直接放回    → 3 [5, 9] 6 2 4 7 1 8
 
第3轮 i=2：tmp = 6
  9 > 6 → 9 后移        → 3 5 [_, 9] 2 4 7 1 8
  5 > 6 ? 否            → 3 [5, 6, 9] 2 4 7 1 8
 
第4轮 i=3：tmp = 2
  9, 6, 5, 3 全部比 2 大，依次后移
                        → [_, 3, 5, 6, 9] 4 7 1 8
  2 放入位置0           → [2, 3, 5, 6, 9] 4 7 1 8
 
第5轮 i=4：tmp = 4
  9, 6, 5 后移，3 比 4 小停
                        → 2 3 [4, 5, 6, 9] 7 1 8
 
第6轮 i=5：tmp = 7
  9 后移，6 比 7 小停    → 2 3 4 5 6 [7, 9] 1 8
 
第7轮 i=6：tmp = 1
  9, 7, 6, 5, 4, 3, 2 全部后移
                        → [1, 2, 3, 4, 5, 6, 7, 9] 8
 
第8轮 i=7：tmp = 8
  9 后移，7 比 8 小停    → 1 2 3 4 5 6 7 [8, 9]
 
结果：    1  2  3  4  5  6  7  8  9

数组下标：  0  1  2  3  4  5  6  7  8
元素值：    5  3  9  6  2  4  7  1  8
分组：      ▲  ●  ■  ★  ▲  ●  ■  ★  ▲
 
▲ 组（下标 0,4,8）：5, 2, 8   → 插入排序后 2, 5, 8
● 组（下标 1,5）：   3, 4      → 插入排序后 3, 4
■ 组（下标 2,6）：   9, 7      → 插入排序后 7, 9
★ 组（下标 3,7）：   6, 1      → 插入排序后 1, 6
 
gap=4 预排序后：  2  3  7  1  5  4  9  6  8

// 希尔排序：缩小增量法，对直接插入排序的优化
void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;   // 推荐写法：除以 3 加 1，保证最后一次 gap 恰好为 1
 
        // 下面这段就是"分组版"的直接插入排序：
        // 把直接插入排序里所有的相邻移动（end+1 / end-1）换成隔 gap 移动
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];   // 待插入元素在 gap 个位置之后
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];  // 大元素向后跳 gap 个位置
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

gap × [1 + 2 + 3 + ... + (n/gap - 1)]

// 直接选择排序（进阶版）：每轮同时选出最小值和最大值
// begin 指向待排序区间起点，end 指向终点；mini/maxi 记录最小/最大值下标
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int mini = begin, maxi = begin;   // 先假设 begin 位置既是最小又是最大
        for (int i = begin; i <= end; i++)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;   // 记录更大的元素下标
            }
            if (a[i] < a[mini])
            {
                mini = i;   // 记录更小的元素下标
            }
        }
 
        // 关键处理：如果最大值正好在 begin 位置（区间起点），
        // 那么 mini 与 begin 交换后，最大值会被换到 mini 原来所在的位置，
        // 所以必须让 maxi 指向 mini，第二次交换才能把真正的最大值放到末尾
        if (begin == maxi)
        {
            maxi = mini;
        }
 
        swap(&a[mini], &a[begin]);   // 最小值放到区间开头
        swap(&a[maxi], &a[end]);     // 最大值放到区间末尾
 
        ++begin;
        --end;
    }
}

初始：      5  3  9  6  2  4  7  1  8
下标：      0  1  2  3  4  5  6  7  8
 
第1轮 begin=0, end=8：min=1(下标7)，max=9(下标2)，begin!=maxi
  交换 a[7]↔a[0]   →  1  3  9  6  2  4  7  5  8
  交换 a[2]↔a[8]   →  1  3  8  6  2  4  7  5  9
 
第2轮 begin=1, end=7：min=2(下标4)，max=8(下标2)，begin!=maxi
  交换 a[4]↔a[1]   →  1  2  8  6  3  4  7  5  9
  交换 a[2]↔a[7]   →  1  2  5  6  3  4  7  8  9
 
第3轮 begin=2, end=6：min=3(下标4)，max=7(下标6)，begin!=maxi
  交换 a[4]↔a[2]   →  1  2  3  6  5  4  7  8  9
  交换 a[6]↔a[6]   →  1  2  3  6  5  4  7  8  9   （最大值已在末尾，原地交换）
 
第4轮 begin=3, end=5：区间 {6,5,4}，min=4(下标5)，max=6(下标3)
  begin == maxi 成立！先把 maxi 改为 mini（即5）
  交换 a[5]↔a[3]   →  1  2  3  4  5  6  7  8  9
  交换 a[5]↔a[5]   →  1  2  3  4  5  6  7  8  9
 
结果：      1  2  3  4  5  6  7  8  9

// 向下调整算法：把以 parent 为根的子树调整成大堆
// 前提：parent 的左右子树已经是大堆
// n 为当前堆的有效元素个数（堆排序过程中堆在逐渐变小）
void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;   // 先默认取左孩子（完全二叉树左孩子下标 = 2*parent+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)
{
    // 1. 建堆：从最后一个非叶子结点 (n-1-1)/2 开始，逐个向下调整
    //    叶子结点没有孩子，天然满足堆的性质，不需要调整
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
 
    // 2. 排序：把堆顶（当前最大值）换到末尾，再对前面的元素重新建堆
    int end = n - 1;
    while (end > 0)
    {
        swap(&a[0], &a[end]);      // 堆顶最大值放到数组末尾
        AdjustDown(a, end, 0);     // 重新调整 [0, end) 区间为大堆
        --end;
    }
}

初始数组：      5  3  9  6  2  4  7  1  8
下标：          0  1  2  3  4  5  6  7  8
最后一个非叶子结点：(9-1-1)/2 = 3，即 a[3]=6
 
AdjustDown(3)：孩子 a[7]=1、a[8]=8，选较大的 8，8>6 交换
                →  5  3  9  8  2  4  7  1  6
AdjustDown(2)：孩子 a[5]=4、a[6]=7，7>9？否，不动
AdjustDown(1)：孩子 a[3]=8、a[4]=2，8>3 交换；继续沉，a[7]=1、a[8]=6，6>3 交换
                →  5  8  9  6  2  4  7  1  3
AdjustDown(0)：孩子 a[1]=8、a[2]=9，9>5 交换；继续沉，a[5]=4、a[6]=7，7>5 交换
                →  9  8  7  6  2  4  5  1  3
建堆完成：堆顶 a[0]=9 是最大值
 
排序阶段（堆顶与末尾交换 + 重新调整）：
交换 a[0]↔a[8]：3  8  7  6  2  4  5  1 [9]    调整 → 8  6  7  3  2  4  5  1 [9]
交换 a[0]↔a[7]：1  6  7  3  2  4  5 [8  9]    调整 → 7  6  5  3  2  4  1 [8  9]
交换 a[0]↔a[6]：1  6  5  3  2  4 [7  8  9]    调整 → 6  3  5  1  2  4 [7  8  9]
交换 a[0]↔a[5]：4  3  5  1  2 [6  7  8  9]    调整 → 5  3  4  1  2 [6  7  8  9]
交换 a[0]↔a[4]：2  3  4  1 [5  6  7  8  9]    调整 → 4  3  2  1 [5  6  7  8  9]
交换 a[0]↔a[3]：1  3  2 [4  5  6  7  8  9]    调整 → 3  1  2 [4  5  6  7  8  9]
交换 a[0]↔a[2]：2  1 [3  4  5  6  7  8  9]    调整 → 2  1 [3  4  5  6  7  8  9]
交换 a[0]↔a[1]：1 [2  3  4  5  6  7  8  9]    完成！

// 冒泡排序：每轮把最大的元素"冒"到数组末尾
void BubbleSort(int* a, int n)
{
    // 内层循环每完成一轮，末尾就多一个就位的最大元素
    // 所以第 i 轮只需要比较前 n-i-1 对相邻元素
    for (int i = 0; i < n; i++)
    {
        int exchange = 0;   // 优化标志：记录本轮是否发生过交换
 
        for (int j = 0; j < n - i - 1; j++)
        {
            if (a[j] > a[j + 1])   // 相邻元素比较，大的往后换
            {
                exchange = 1;
                swap(&a[j], &a[j + 1]);
            }
        }
 
        // 如果一整轮都没有发生交换，说明数组已经有序，提前结束
        if (exchange == 0)
        {
            break;
        }
    }
}

初始：      5  3  9  6  2  4  7  1  8
 
第1轮：相邻两两比较，9 一路"冒"到末尾
          3  5  6  2  4  7  1  8 [9]
第2轮：8 冒到倒数第二
          3  5  2  4  6  1  7 [8  9]
第3轮：7 就位
          3  2  4  5  1  6 [7  8  9]
第4轮：6 就位
          2  3  4  1  5 [6  7  8  9]
第5轮：5 就位
          2  3  1  4 [5  6  7  8  9]
第6轮：4 就位
          2  1  3 [4  5  6  7  8  9]
第7轮：3 就位
          1  2 [3  4  5  6  7  8  9]
第8轮：扫描一遍发现一次交换都没发生，exchange 保持 0，提前退出
结果：   1  2  3  4  5  6  7  8  9

// 快速排序主框架：left、right 是闭区间 [left, right] 的左右端点
void QuickSort(int* a, int left, int right)
{
    if (left >= right)   // 区间为空或只有一个元素，天然有序，返回
    {
        return;
    }
 
    // _QuickSort 负责单趟划分：以基准值为界把 [left, right] 分成两半
    // 返回基准值最终所在的下标 meet
    int meet = _QuickSort(a, left, right);
 
    QuickSort(a, left, meet - 1);    // 递归处理左子区间
    QuickSort(a, meet + 1, right);   // 递归处理右子区间
}

// hoare 版本单趟划分：右边找小、左边找大，交换；最终把基准值放到相遇位置
int _QuickSort(int* a, int left, int right)
{
    int begin = left;    // 保存左端点（基准值位置）
    int end = right;     // 保存右端点
    int keyi = left;     // 基准值下标，先取最左边的元素
 
    ++left;              // 左右指针从基准值的下一个位置开始扫描
    while (left <= right)
    {
        // 右边找小：跳过所有比基准值大的元素，停在第一个小于等于基准值的位置
        while (left <= right && a[right] > a[keyi])
        {
            --right;
        }
        // 左边找大：跳过所有比基准值小的元素，停在第一个大于等于基准值的位置
        while (left <= right && a[left] < a[keyi])
        {
            ++left;
        }
        // 两边都找到了，交换（相等值也要交换，原因见下文），指针各自向中间收拢
        if (left <= right)
        {
            swap(&a[left++], &a[right--]);
        }
    }
    // 循环结束，right 指向的位置必然不大于基准值，把基准值放过去
    swap(&a[keyi], &a[right]);
    return right;   // 基准值最终位置
}

初始：5  3  9  6  2  4  7  1  8        key = 5, left = 1, right = 8
      ↑key                           ↑left           ↑right
 
第1次扫描：右找小：8、7 > 5 跳过，1 < 5 停 → right = 7
          左找大：3 < 5 跳过，9 > 5 停 → left = 2
          交换 a[2] ↔ a[7]：5  3  1  6  2  4  7  9  8    left = 3, right = 6
 
第2次扫描：右找小：7 > 5 跳过，4 < 5 停 → right = 5
          左找大：6 > 5 停 → left = 3
          交换 a[3] ↔ a[5]：5  3  1  4  2  6  7  9  8    left = 4, right = 4
 
第3次扫描：右找小：2 < 5 停 → right = 4
          左找大：2 < 5 跳过跳到下标5；left(5) 已越过 right(4)，内层退出
          left(5) > right(4)，循环结束
 
把基准值与 right 位置交换：2  3  1  4  5  6  7  9  8    return 4

                 [2 3 1 4] 5 [6 7 9 8]         ← 第一趟划分
                 /            \
        [1] 2 [3 4]           [6 7] 8 [9]      ← 第二趟划分
              /                \
           [3] 4            [6] 7               ← 第三趟划分
           ...
最终：1 2 3 4 5 6 7 8 9

// 挖坑法单趟划分：基准值先"挖"出来留坑，左右交替填坑，最后把基准值填回坑中
int _QuickSort(int* a, int left, int right)
{
    int key = a[left];   // 先把基准值挖出来存好
    int hole = left;     // 基准值原来的位置就是一个"坑"
 
    while (left < right)
    {
        // 右边找小：找到比 key 小的元素，填进左边的坑，自己变成新坑
        while (left < right && a[right] >= key)
        {
            --right;
        }
        a[hole] = a[right];   // 填坑
        hole = right;         // 新坑
 
        // 左边找大：找到比 key 大的元素，填进右边的坑，自己变成新坑
        while (left < right && a[left] <= key)
        {
            ++left;
        }
        a[hole] = a[left];    // 填坑
        hole = left;          // 新坑
    }
    a[hole] = key;   // 左右指针相遇，把基准值填进最后一个坑
    return hole;
}

初始：5  3  9  6  2  4  7  1  8        key = 5, 坑在 0
      ↑l                     ↑r
右找小：8、7 ≥ 5 跳过，1 < 5 停（right = 7），a[7] 填入坑0，坑移到7
      →  1  3  9  6  2  4  7  _  8     （位置7现在是坑）
左找大：3 ≤ 5 跳过，9 > 5 停（left = 2），a[2] 填入坑7，坑移到2
      →  1  3  _  6  2  4  7  9  8     （位置2现在是坑）
右找小：7 ≥ 5 跳过，4 < 5 停（right = 5），a[5] 填入坑2，坑移到5
      →  1  3  4  6  2  _  7  9  8     （位置5现在是坑）
左找大：6 > 5 停（left = 3），a[3] 填入坑5，坑移到3
      →  1  3  4  _  2  6  7  9  8     （位置3现在是坑）
右找小：2 < 5 停（right = 4），a[4] 填入坑3，坑移到4
      →  1  3  4  2  _  6  7  9  8     （位置4现在是坑）
左找大：2 ≤ 5 跳过，left 与 right 相遇（4 == 4），循环结束
把 key 填进最后一个坑：1  3  4  2  5  6  7  9  8    return 4

// lomuto 前后指针法单趟划分：cur 找小，与 prev 交换，把小元素都集中到左侧
int _QuickSort(int* a, int left, int right)
{
    int prev = left, cur = left + 1;   // prev 指向已排好的小元素末尾，cur 负责向后扫描
    int key = left;                    // 基准值下标，取最左边元素
 
    while (cur <= right)
    {
        // 找到比基准值小的元素：
        // 先 ++prev 指向下一个待交换位置，如果 prev 和 cur 重合就无需交换
        if (a[cur] < a[key] && ++prev != cur)
        {
            swap(&a[cur], &a[prev]);
        }
        ++cur;
    }
    // 最后把基准值换到 prev 位置，它左边全是小于它的元素
    swap(&a[key], &a[prev]);
    return prev;
}

初始：5  3  9  6  2  4  7  1  8       prev = 0, cur = 1
      ↑k ↑p                          ↑c
 
cur=1：a[1]=3 < 5，++prev=1，1==cur 不交换          cur→2
cur=2：a[2]=9 < 5? 否                                cur→3
cur=3：a[3]=6 < 5? 否                                cur→4
cur=4：a[4]=2 < 5，++prev=2，2≠4，交换 a[2]↔a[4]
      →  5  3  2  6  9  4  7  1  8                  cur→5
cur=5：a[5]=4 < 5，++prev=3，3≠5，交换 a[3]↔a[5]
      →  5  3  2  4  9  6  7  1  8                  cur→6
cur=6：a[6]=7 < 5? 否                                cur→7
cur=7：a[7]=1 < 5，++prev=4，4≠7，交换 a[4]↔a[7]
      →  5  3  2  4  1  6  7  9  8                  cur→8
cur=8：a[8]=8 < 5? 否                                cur→9 结束
 
最后把基准值换到 prev=4：1  3  2  4  5  6  7  9  8    return 4

// 快速排序非递归版本：借助栈模拟递归，避免系统栈溢出风险
void QuickSortNonR(int* a, int left, int right)
{
    ST st;              // 顺序栈（数据结构章节实现）
    STInit(&st);
    STPush(&st, right); // 先压右端点，再压左端点（注意压栈顺序）
    STPush(&st, left);
 
    while (!STEmpty(&st))
    {
        // 弹出区间 [begin, end]（栈是后进先出，先弹 left）
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);
 
        // 单趟划分，这里用 lomuto 前后指针法
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        while (cur <= end)
        {
            if (a[cur] < a[keyi] && ++prev != cur)
            {
                swap(&a[prev], &a[cur]);
            }
            ++cur;
        }
        swap(&a[keyi], &a[prev]);
        keyi = prev;
 
        // 划分结果：[begin, keyi-1]  keyi  [keyi+1, end]
        // 把非空的左右子区间压栈，等待下一轮处理
        if (keyi + 1 < end)   // 右区间非空
        {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1) // 左区间非空
        {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
 
    STDestroy(&st);
}

// 三数取中：返回 a[left]、a[mid]、a[right] 三者中位数的下标
int GetMidIndex(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right]) return mid;        // left < mid < right
        else if (a[left] > a[right]) return left; // right < left < mid
        else return right;                        // left < right < mid
    }
    else   // a[left] >= a[mid]
    {
        if (a[mid] > a[right]) return mid;        // right < mid < left
        else if (a[left] < a[right]) return left; // mid < left < right
        else return right;                        // mid < right < left
    }
}

// 优化后的快排：三数取中 + 小区间插入排序
void QuickSort(int* a, int left, int right)
{
    if (left >= right)              // 区间为空或单元素，天然有序
        return;
 
    // 优化二：小区间插入排序。
    // 区间缩小到 <= 10 个元素时，递归的"函数调用 + 栈帧"开销开始大于
    // 直接插入排序本身，而且此时区间已接近有序，插入排序几乎 O(N)——
    // 用插入排序收尾，既省递归开销，又吃到"近似有序"的红利
    if (right - left + 1 <= 10)
    {
        InsertSort(a + left, right - left + 1);
        return;
    }
 
    // 优化一：三数取中，把中位数换到 left 当基准
    int mid = GetMidIndex(a, left, right);
    if (mid != left)
        swap(&a[mid], &a[left]);
 
    int keyi = _QuickSort(a, left, right);   // 单趟划分（hoare/挖坑/lomuto 任选）
    QuickSort(a, left, keyi - 1);            // 递归左区间
    QuickSort(a, keyi + 1, right);           // 递归右区间
}

            [5 3 9 6 2 4 7 1 8]               ← 原数组
            /                 \
      [5 3 9 6 2]           [4 7 1 8]
      /        \             /      \
   [5 3 9]    [6 2]       [4 7]    [1 8]
   /    \     /  \        /  \     /  \
 [5]  [3 9] [6] [2]     [4] [7]  [1] [8]     ← 递归到底，单元素天然有序
   \    /     \  /        \  /     \  /
   [3 5 9]   [2 6]       [4 7]    [1 8]       ← 开始两两合并
      \       /             \      /
     [2 3 5 6 9]           [1 4 7 8]          ← 合并出两个有序序列
              \             /
            [1 2 3 4 5 6 7 8 9]               ← 最终合并

左序列：2  3  5  6  9       右序列：1  4  7  8        tmp 数组
 ↑l                         ↑r
比较 2 和 1：1 小 → 拷入 tmp         →  tmp: [1]
 ↑l                         ↑r→4
比较 2 和 4：2 小 → 拷入 tmp         →  tmp: [1 2]
 ↑l→3                       ↑r
比较 3 和 4：3 小 → 拷入 tmp         →  tmp: [1 2 3]
比较 5 和 4：4 小 → 拷入 tmp         →  tmp: [1 2 3 4]
比较 5 和 7：5 小 → 拷入 tmp         →  tmp: [1 2 3 4 5]
比较 6 和 7：6 小 → 拷入 tmp         →  tmp: [1 2 3 4 5 6]
比较 9 和 7：7 小 → 拷入 tmp         →  tmp: [1 2 3 4 5 6 7]
比较 9 和 8：8 小 → 拷入 tmp         →  tmp: [1 2 3 4 5 6 7 8]
右序列耗尽，把左序列剩余的 9 拷入   →  tmp: [1 2 3 4 5 6 7 8 9]

// 归并排序的子函数：把 [left, mid] 和 [mid+1, right] 两个有序区间合并
// tmp 是提前申请好的辅助数组，长度为 n
void _MergeSort(int* a, int left, int right, int* tmp)
{
    if (left >= right)   // 区间为空或只有一个元素，天然有序
    {
        return;
    }
    int mid = (right + left) / 2;   // 分成两个子区间
    // [left, mid] 和 [mid+1, right]
 
    // 1. 先递归，让两个子区间各自有序
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);
 
    // 2. 合并两个有序子区间到 tmp 中
    int begin1 = left, end1 = mid;      // 左子区间 [begin1, end1]
    int begin2 = mid + 1, end2 = right; // 右子区间 [begin2, end2]
    int index = begin1;                 // 写入 tmp 的起始位置
 
    while (begin1 <= end1 && begin2 <= end2)
    {
        // 谁小谁先进 tmp；相等时取左序列的元素（<=），保证稳定性
        if (a[begin1] <= a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
    }
    // 某个子区间先耗尽，把另一个子区间的剩余元素全部拷入
    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }
 
    // 3. 把合并结果从 tmp 拷回原数组的对应区间
    for (int i = left; i <= right; i++)
    {
        a[i] = tmp[i];
    }
}
 
// 归并排序入口：申请辅助数组，调用子函数，释放内存
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);   // C 语言用 malloc 申请
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);   // 记得释放
}

gap = 1： [5][3]→[3 5]   [9][6]→[6 9]   [2][4]→[2 4]   [7][1]→[1 7]   [8]
gap = 2： [3 5]+[6 9]→[3 5 6 9]        [2 4]+[1 7]→[1 2 4 7]        [8]
gap = 4： [3 5 6 9]+[1 2 4 7]→[1 2 3 4 5 6 7 9]                     [8]
gap = 8： 整体归并，完成

// 归并排序非递归版本：gap 从 1 开始倍增，相邻两个 gap 大小的区间两两归并
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);   // 辅助数组
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }
 
    int gap = 1;                     // 每轮归并的子区间长度
    while (gap < n)
    {
        // 每轮把数组按 2*gap 切成若干组，每组含左右两个 gap 长的子区间
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;       // 左子区间 [begin1, end1]
            int begin2 = i + gap, end2 = i + 2 * gap - 1; // 右子区间 [begin2, end2]
 
            // 边界处理一：右子区间根本不存在（begin2 越界），本组只有一个子区间，
            // 它已经有序，无需合并（也不要动它）
            if (begin2 >= n)
                break;
 
            // 边界处理二：右子区间不完整（end2 越界），把它截断到 n-1
            if (end2 >= n)
                end2 = n - 1;
 
            // 合并两个有序子区间到 tmp（和递归版完全相同的归并逻辑）
            int index = i;
            int b1 = begin1, e1 = end1, b2 = begin2, e2 = end2;
            while (b1 <= e1 && b2 <= e2)
            {
                if (a[b1] <= a[b2])          // 相等取左，保持稳定
                    tmp[index++] = a[b1++];
                else
                    tmp[index++] = a[b2++];
            }
            while (b1 <= e1)
                tmp[index++] = a[b1++];
            while (b2 <= e2)
                tmp[index++] = a[b2++];
 
            // 把本组归并结果从 tmp 拷回原数组的对应区间
            for (int j = begin1; j <= end2; j++)
                a[j] = tmp[j];
        }
        gap *= 2;                        // 归并长度翻倍
    }
 
    free(tmp);
}

// 计数排序：统计元素出现次数，再按次数回收（数据范围集中时效率极高）
void CountSort(int* a, int n)
{
    // 1. 遍历数组，找出最小值和最大值
    int min = a[0], max = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
        if (a[i] < min)
        {
            min = a[i];
        }
    }
 
    // 2. 申请计数数组，长度为数据范围
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    if (count == NULL)
    {
        perror("malloc fail");
        return;
    }
    memset(count, 0, sizeof(int) * range);   // 计数数组清零
 
    // 3. 统计每个元素出现的次数
    //    元素 a[i] 映射到下标 a[i] - min
    for (int i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }
 
    // 4. 按次数把元素回收回原数组
    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (count[i]--)   // 出现几次就写几个
        {
            a[j++] = i + min;   // 下标 i 对应元素值 i + min
        }
    }
 
    free(count);   // 释放计数数组
}

元素值：      1  2  3  4  5  6  7  8  9
下标(i)：     0  1  2  3  4  5  6  7  8
count[i]：    1  1  1  1  1  1  1  1  1     ← 每个元素恰好出现一次
 
回收：从下标0到8，依次写入 i+min：
       1  2  3  4  5  6  7  8  9

元素值：      1  2  3  4  5  6  7  8  9
count[i]：    1  1  2  1  2  1  1  1  1
回收：       1  2  3  3  4  5  5  6  7  8  9

// 测试排序的性能对比：100000 个随机数，7 种排序各测一遍
void TestOP()
{
    srand(time(0));
    const int N = 100000;
 
    // 准备 7 份完全相同的数据
    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);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[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);
    int end3 = clock();
 
    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();
 
    int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();
 
    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();
 
    int begin7 = clock();
    BubbleSort(a7, N);
    int end7 = clock();
 
    // 打印耗时（单位：毫秒）
    printf("InsertSort:%dms\n", end1 - begin1);
    printf("ShellSort:%dms\n", end2 - begin2);
    printf("SelectSort:%dms\n", end3 - begin3);
    printf("HeapSort:%dms\n", end4 - begin4);
    printf("QuickSort:%dms\n", end5 - begin5);
    printf("MergeSort:%dms\n", end6 - begin6);
    printf("BubbleSort:%dms\n", end7 - begin7);
 
    // 释放内存
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
}

InsertSort:2600ms      ← O(N²) 级别，肉眼可见的慢
ShellSort:20ms         ← 希尔排序的威力：比插入快一百多倍
SelectSort:2800ms      ← O(N²) 级别
HeapSort:15ms          ← O(NlogN) 级别
QuickSort:10ms         ← 常数因子小，O(NlogN) 里最快
MergeSort:20ms         ← 稳定但要多一份空间
BubbleSort:6000ms      ← O(N²) 里最慢，垫底