数据结构常见排序算法汇总：插入、交换、选择与归并

插入排序

直接插入排序

思路

当处理到第 i 个数的时候，[1, i-1] 是有序的，我们希望找到一个 j，使得 [1, j] <= a[i] < [j+1, i-1]。

代码

//=====================================
// 直接插入排序
//=====================================
void InsertSort(SqList& L) {
    // 首先第一个元素我们认为是有序的，从第二个元素开始，直到最后一个元素
    for (int i = 2; i <= L.length; ++i) {
        // 对于每一个待处理的元素，如果与前一个元素没有逆序的话，那就不用插入到前面去了
        // 如果有逆序的话，那要插入到前面去
        if (L.r[i - 1].key > L.r[i].key) {
            // 寻找插入的位置
            // 首先保存好第 i 个元素的数据，因为我们每在前面找到一个大于当前元素的值，就会让这个元素往右覆盖，自然会覆盖到第 i 个元素的数据
            L.r[0] = L.r[i];
            // 我们希望找到最右边的，小于或者等于 a[i] 的元素的下标
            // 为什么还要考虑等于呢？如果只是找到小于的，最后第 i 个元素会插入到所有相同元素的最前面（如果有相同元素），这样会破坏排序的稳定性（相同元素顺序不变）
            int j;
            // 如果元素 j 还是大于元素 i 的话，那就继续往前找，并把元素 j 右覆盖
            // 直到小于等于元素 i，得到的 j 是最右边的，小于或者等于 a[i] 的元素的下标
            // 这个时候 j 的右边有一个空位，刚刚好可以用来插入元素 i 的数据
            // 考虑极端情况如果右边的元素都比 i 大呢，这样最后 j=0，因为元素 0 被赋值了，肯定和元素 i 相等，那么只需要把 j+1 也就是第 1 个元素的值赋值为元素 i 就行
            for (j = i - 1; L.r[0].key < L.r[j].key; --j) {
                L.r[j + 1] = L.r[j];
            }
            L.r[j + 1] = L.r[0];
        }
    }
}

折半查找插入排序

思路

优化插入排序的查找方法，使用折半查找。当处理到第 i 个数的时候，[1, i-1] 是有序的，符合折半查找的前提条件。采用左闭右闭写法，有效区间是 low <= high。

代码

//=====================================
// 折半查找插入排序
//=====================================
void BInsertSort(SqList& L) {
    for (int i = 2; i <= L.length; ++i) {
        // 在 1 到 i-1 找一个符合要求的位置
        if (L.r[i].key < L.r[i - 1].key) {
            int low = 1, high = i - 1;
            L.r[0] = L.r[i];
            // 二分模板
            while (low <= high) {
                // 为了防止溢出，所以要写成 low+(high-low)/2，左移 1 位就是除以 2，左移效率更高
                // 位运算优先级比较低，所以要加上括号
                int mid = low + ((high - low) >> 1);
                if (L.r[mid].key > L.r[0].key) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            int j;
            // 手动模拟一下数据就可以知道了，low=high+1
            for (j = i - 1; j >= low; --j) {
                L.r[j + 1] = L.r[j];
            }
            L.r[j + 1] = L.r[0];
        }
    }
}

希尔排序

思路

希尔排序是插入排序的优化版本，通过缩小增量进行分组插入。

代码

//=====================================
// 希尔排序 / 缩小增量排序
//=====================================
void ShellSort(SqList& L) {
    for (int d = L.length / 2; d > 0; d /= 2) {
        // 我发现第 i+d 个数只需要先第 i 个数比较就行
        // 如果正序，那就不用插入了；如果逆序，再考虑插入
        for (int i = 1 + d; i <= L.length; i++) {
            // 逆序了，所以得插入
            if (L.r[i].key < L.r[i - d].key) {
                L.r[0] = L.r[i];
                int j;
                // 这里的逻辑和直接插入排序一模一样，只是步长从 1 变成了 d
                for (j = i - d; j > 0 && L.r[0].key < L.r[j].key; j -= d) {
                    L.r[j + d] = L.r[j];
                }
                L.r[j + d] = L.r[0];
            }
        }
    }
}

交换排序

冒泡排序

思路

相邻元素两两比较，将较大的元素逐步移动到序列末尾。

代码

//=====================================
// 冒泡排序
//=====================================
void BubbleSort(SqList& L) {
    auto& r = L.r;
    bool change; // true：有逆序，false：无逆序
    // 最开始假设有逆序（不然不用排序了），所以 change=true
    for (int i = L.length, change = true; i > 1 && change; --i) {
        // 没有逆序是 false，这个时候循环条件不成立，循环结束
        // 每次都要初始化为没有逆序
        change = false;
        for (int j = 1; j < i; ++j) {
            // 只有左边大于右边才会交换
            // 如果左右相等就不会交换，所以我认为是冒泡排序可以是稳定的
            // 如果是>=的话，就不是稳定的了
            if (r[j].key > r[j + 1].key) {
                swap(r[j], r[j + 1]);
                change = true; // 存在逆序
            }
        }
    }
}

快速排序

思路

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。

严蔚敏数据结构版本

// =====================================
// 快速排序
// =====================================
//=========课本版本，除了 auto 是我加上去的=========
int Partition(SqList& L, int low, int high) {
    auto& r = L.r;
    r[0] = r[low];
    while (low < high) {
        while (low < high && r[high].key >= r[0].key) --high;
        // 找到一个 r[high]<r[0] 的，然后把这个移动到左边区域
        r[low] = r[high];
        while (low < high && r[0].key >= r[low].key) ++low;
        // 找到一个 r[low]>r[0] 的，然后移动到右边区域
        r[high] = r[low];
    }
    r[low] = r[0];
    return low;
}

void QuickSort(SqList& L, int low, int high) {
    if (low >= high) return;
    int p = Partition(L, low, high);
    QuickSort(L, low, p - 1);
    QuickSort(L, p + 1, high);
}

优化 1：用栈模拟递归

//=========栈版本=========
void QuickSort_Stack(SqList& L) {
    stack<pair<int, int>> S;
    auto& r = L.r;
    S.push({1, L.length});
    while (S.size()) {
        auto e = S.top();
        S.pop();
        int low = e.first;
        int high = e.second;
        r[0] = r[low];
        while (low < high) {
            while (low < high && r[high].key >= r[0].key) --high;
            r[low] = r[high];
            while (low < high && r[low].key <= r[0].key) ++low;
            r[high] = r[low];
        }
        r[low] = r[0];
        // =========普通版本=========
        /*if (e.first < low - 1) S.push({e.first, low - 1});
        if (e.second > low + 1) S.push({low + 1, e.second});*/
        // =========优化版本=========
        int leftLen = (low - 1) - e.first;
        int rightLen = e.second - (low + 1);
        if (leftLen > rightLen) {
            // 左边更长，先压左边（保证它在栈底），后压右边
            if (leftLen > 0) S.push({e.first, low - 1});
            if (rightLen > 0) S.push({low + 1, e.second});
        } else {
            // 右边更长，先压右边，后压左边
            if (rightLen > 0) S.push({low + 1, e.second});
            if (leftLen > 0) S.push({e.first, low - 1});
        }
    }
}

优化 2：优化取枢轴 随机取数

//=========随机选择枢纽版本=========
// 这个函数只负责选枢纽，并把它换到 low 位置
// 这样 Partition 函数内部就不用关心枢纽是怎么选出来的了
void SelectPivotRandom(SqList& L, int low, int high) {
    // 生成 [low, high] 范围内的随机索引
    int pivotPos = low + rand() % (high - low + 1);
    // 把随机选中的数交换到 low 位置
    // 这样原有的 Partition 逻辑可以直接复用 r[low] 作为枢纽
    std::swap(L.r[low], L.r[pivotPos]);
}

int Partition_Random(SqList& L, int low, int high) {
    // 1. 【标准做法】先执行随机选取策略
    SelectPivotRandom(L, low, high);
    // 2. 下面就是你熟悉的挖坑法，一行都不用改
    auto& r = L.r;
    r[0] = r[low]; // 这里的 r[low] 已经是随机选来的那个值了
    while (low < high) {
        while (low < high && r[high].key >= r[0].key) --high;
        r[low] = r[high];
        while (low < high && r[low].key <= r[0].key) ++low;
        r[high] = r[low];
    }
    r[low] = r[0];
    return low;
}

void QuickSort_Random(SqList& L, int low, int high) {
    if (low >= high) return;
    int p = Partition(L, low, high);
    QuickSort(L, low, p - 1);
    QuickSort(L, p + 1, high);
}

优化 3：优化取枢轴 三数取中

//=========三数取中版本=========
// 1. 辅助函数：三数取中并交换到头部
// 命名后缀：_MedianOfThree
void SelectPivot_MedianOfThree(SqList& L, int low, int high) {
    int mid = low + (high - low) / 2;
    auto& r = L.r;
    // 逻辑：先把 low, mid, high 三个位置的数排个序
    // 目标顺序：r[low] <= r[mid] <= r[high]
    // 如果左边比中间大，交换（保证左 <= 中）
    if (r[low].key > r[mid].key) std::swap(r[low], r[mid]);
    // 如果左边比右边大，交换（保证左 <= 右）
    // 经过这两步，r[low] 肯定是三个数里最小的
    if (r[low].key > r[high].key) std::swap(r[low], r[high]);
    // 现在只需比较中和右。如果中比右大，交换
    // 这样就变成了：r[low] <= r[mid] <= r[high]
    if (r[mid].key > r[high].key) std::swap(r[mid], r[high]);
    // 此时，r[mid] 就是当之无愧的'中位数'
    // 我们把它换到 low 的位置，作为接下来的基准（枢纽）
    std::swap(r[low], r[mid]);
}

// 2. 划分函数：使用三数取中策略
// 命名后缀：_MedianOfThree
int Partition_MedianOfThree(SqList& L, int low, int high) {
    // 这一步是唯一的区别：先调整基准值
    SelectPivot_MedianOfThree(L, low, high);
    // ==========================================
    // 下面是标准的'挖坑法'逻辑，完全复用之前的代码
    // ==========================================
    auto& r = L.r;
    r[0] = r[low]; // 这里的 r[low] 已经是刚才选好的中位数了
    while (low < high) {
        // 右边找小的
        while (low < high && r[high].key >= r[0].key) --high;
        r[low] = r[high]; // 填入左坑
        // 左边找大的
        while (low < high && r[low].key <= r[0].key) ++low;
        r[high] = r[low]; // 填入右坑
    }
    r[low] = r[0]; // 基准归位
    return low;
}

// 3. 递归主函数
// 命名后缀：_MedianOfThree
void QuickSort_MedianOfThree(SqList& L, int low, int high) {
    if (low >= high) return;
    // 调用新的划分函数
    int p = Partition_MedianOfThree(L, low, high);
    // 递归处理左右子表
    QuickSort_MedianOfThree(L, low, p - 1);
    QuickSort_MedianOfThree(L, p + 1, high);
}

选择排序

简单选择排序

思路

• 把 1 到 n 的最小值放到 1
• 把 2 到 n 的最小值放到 2
• ……
• 把 n-1 到 n 的最小值放到 n-1
• n 到 n 只有一个数据，不用理了
• 所以每次都是找第 i 到 n 的最小值，放到第 i 个位置里
• 如果 i 本身就是最小值，就不需要交换了

代码

// =====================================
// 简单选择排序
// =====================================
void SelectSort(SqList& L) {
    auto& r = L.r;
    // 思路：把 1 到 n 的最小值放到 1，把 2 到 n 的最小值放到 2……
    // 所以每次都是找第 i 到 n 的最小值，放到第 i 个位置里
    // 如果 i 本身就是最小值，就不需要交换了
    // i 代表当前要确定的位置 (1 到 n-1)
    // 也就是说，确定第 i 个位置的值、第 i 到 n 的最小值是多少
    for (int i = 1; i < L.length; ++i) {
        int minIdx = i; // 先假设自己就是最小的
        // 从 i+1 开始往后找，看看有没有更小的
        for (int j = i + 1; j <= L.length; ++j) {
            if (r[j].key < r[minIdx].key) minIdx = j;
        }
        // 如果最小的不是自己，就交换
        if (minIdx != i) {
            swap(r[i], r[minIdx]);
        }
    }
}

树形选择排序

思路

利用锦标赛树的思想进行选择。

代码

// =====================================
// 树形选择排序
// =====================================
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>

void TreeSelectionSort(SqList& L) {
    int n = L.length;
    // 1. 准备辅助空间
    // 树形排序需要把原数组补成一个满二叉树（叶子数为 2 的幂次）
    // 比如 n=5，需要补到 8 (2^3)
    int leafSize = 1;
    while (leafSize < n) leafSize *= 2;
    // treeSize 是节点总数，大小约为 2 * leafSize
    // tree 数组存储的是原数据在 L.r 中的【下标】，而不是值
    // 这样做是为了方便我们在'退赛'时找到它在原表中的位置
    int treeSize = 2 * leafSize;
    vector<int> tree(treeSize);

    // 2. 初始化叶子节点 (存储在树数组的后半段)
    // 树的下标从 1 开始，叶子节点从 leafSize 开始
    for (int i = 0; i < leafSize; ++i) {
        if (i < n) {
            // 有实际数据：存储 L.r 中的下标 (1 到 n)
            tree[leafSize + i] = i + 1;
        } else {
            // 补齐的空位：存 -1 表示无穷大/无效
            tree[leafSize + i] = -1;
        }
    }

    // 3. 建立初始锦标赛树 (从下往上，两两比较)
    // i 是父节点，2*i 是左孩子，2*i+1 是右孩子
    for (int i = leafSize - 1; i >= 1; --i) {
        int left = tree[2 * i];
        int right = tree[2 * i + 1];
        // 处理 -1 (无穷大) 的情况
        if (left != -1 && right != -1) {
            // 谁小谁赢，晋级的是【下标】
            if (L.r[left].key <= L.r[right].key) tree[i] = left;
            else tree[i] = right;
        } else if (left != -1) tree[i] = left; // 右边为空，左边自动赢
        else tree[i] = right; // 左边为空，右边自动赢 (或者都是 -1)
    }

    // 4. 临时数组存储排序结果 (树形排序通常是非原地的)
    SqList tempL;
    tempL.length = n;

    // 5. 循环 n 次，每次选出一个最小值
    for (int i = 1; i <= n; ++i) {
        // A. 根节点 (tree[1]) 保存的就是当前冠军的下标
        int minIdx = tree[1];
        tempL.r[i] = L.r[minIdx]; // 将冠军存入临时结果数组
        // B. "退赛"：将该冠军的值设为最大整数 (INT_MAX)
        // 这样它在后续的比较中永远不会赢
        // 注意：这里修改了原数组的值，最后会被 tempL 覆盖回来，所以没关系
        L.r[minIdx].key = INT_MAX;
        // C. "重赛"：从叶子节点开始，沿着刚才冠军的路径向上调整
        // 找到该冠军对应的叶子节点在 tree 数组中的位置
        int idx = leafSize + (minIdx - 1); // minIdx 是 1~n，减 1 对应 0~n-1 偏移
        // 沿着路径向上找父节点重新 PK
        while (idx > 1) {
            int parent = idx / 2;
            int left = tree[2 * parent];
            int right = tree[2 * parent + 1];
            if (left != -1 && right != -1) {
                // 注意：此时之前的冠军值已经变成 INT_MAX 了，所以它肯定会输
                if (L.r[left].key <= L.r[right].key) tree[parent] = left;
                else tree[parent] = right;
            } else if (left != -1) tree[parent] = left;
            else tree[parent] = right;
            idx = parent; // 继续向上
        }
    }
    // 6. 将排序好的数据写回原表
    L = tempL;
}

堆排序

思路

利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

vector 版本

// =====================================
// 堆排序
// =====================================
// 大顶堆
// 自顶到底重新堆化
// 下标从 0 开始的
static void siftDown(vector<int>& a, int n, int i) {
    // n：有效结点的个数，也就是有效下标是 0 到 n-1
    // i:当前处理的结点，在建堆的过程中是从最后一个非叶子节点到根节点（idx=0），在重新堆化的过程是根节点
    while (true) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int maxIdx = i; // 假设 i 是优先级最大的结点
        // 如果 l<n，也就是 l 是有效下标，并且 maxIdx（i）的优先级低，maxIdx=j；
        if (l < n && a[maxIdx] < a[l]) maxIdx = l;
        // 同理
        if (r < n && a[maxIdx] < a[r]) maxIdx = r;
        // 如果最大结点是 i，那么符合堆的逻辑要求
        if (maxIdx == i) break;
        // 如果最大结点不是 i，那么使 i 和 maxIdx 交换
        std::swap(a[i], a[maxIdx]);
        i = maxIdx; // 类似递归，处理下面结点的是否符合堆逻辑要求的问题，与处理当前结点的堆化问题是等价的
        // 等价于 siftDown(a, cmp, n, maxIdx)
    }
}

void my_heap_sort(vector<int>& a) {
    int n = (int)a.size();
    // 1. 建立堆
    // 从最后一个非叶子结点开始堆化
    // 因为叶子节点没有子节点，所以本身就是堆
    // 对于从 0 开始的完全二叉树，知道父节点 i，那么子节点，l=2i+1，r=2i+2
    // 知道子节点 j，那么父节点为 f((i-1)/2), f() 为下取整
    // 由于最后一个结点的下标是 n-1，所以对应父节点，也就是最后一个非叶子节点的下标为
    // f((n-1-1)/2)=f(n/2-1)=f(n/2)-1;
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(a, n, i);
    }
    // 2. 不断交换最后一个结点和根节点，并堆化
    // 从最后一个结点开始交换
    // 也就是 n-1 到 1，单独 0 号结点不用考虑交换，所以跳过
    for (int i = n - 1; i > 0; --i) {
        // 交换根节点（0 到 i 的最大值）与当前最后一个结点（i）
        std::swap(a[i], a[0]);
        // 堆化
        siftDown(a, i, 0);
    }
}

严蔚敏数据结构版本

对于 HeapAdjust：我们可以把它想象成一个'空位下沉'的过程：

1. 挖坑（备份）： rc = H.r[s]。此时，下标 s 的物理空间还在，但在逻辑上，我们把它看作一个'坑'，因为它原来的值已经被保护在 rc 里了。
2. 填坑（上移）： H.r[s] = H.r[j]。我们找到了一个大孩子 j。我们把 j 的值搬上来填补 s 的坑。关键点：此时下标 j 的值虽然还在，但逻辑上 j 变成了新的'坑'。
3. 落坑（归位）： H.r[s] = rc。当 rc 比所有的孩子都大（或者到底了），循环结束。此时 s 指向最终的空位，我们将 rc 放进去。

这种写法 vs swap 写法：

// 严蔚敏数据结构
void HeapAdjust(SqList& H, int s, int m) {
    // s: 当前处理的结点
    // m：最大有效下标
    // 1. 先把要下沉的这个元素（'捣蛋鬼'）存到临时变量 rc 中，挖出一个'坑'
    auto rc = H.r[s]; // 先保存根节点的记录
    // 不断向下找，找到一个结点，这个结点的两个子节点都小于等于 rc
    for (int j = 2 * s; j <= m; j *= 2) {
        if (j < m && H.r[j].key < H.r[j + 1].key) ++j; // 判断左节点还是右节点大，寻找最大结点
        // 如果当前结点的两个子节点都小于等于 rc 的值，那么这个结点可以用来放 rc，不用担心当前结点的值怎么办
        // 如果当前节点是 rc 原来的结点位置，那么当前节点的数据已经被保存在 rc 了
        // 如果不是原来的位置，那么当前结点的值已经被赋值到他的父节点了
        if (!(rc.key < H.r[j].key)) break; // 严蔚敏书中的写法是：if (! (rc.key < H.r[j].key))
        // 翻译成人话就是：if (rc.key >= H.r[j].key)
        // 也就是说：如果'捣蛋鬼'比'最大的孩子'还要大（或相等），说明它已经比该节点的所有子孙都大了（因为堆的性质），那么位置找到了，直接 break，不再下沉。
        // 2. 子节点上移，填补父节点的坑，但父节点不立刻下去，坑移到了子节点位置
        H.r[s] = H.r[j];
        s = j;
        // 3. 更新坑的坐标，也就是说，结点 s 是当前结点 j 的父节点
    }
    H.r[s] = rc; // 4. 循环结束，找到最终位置，把 rc 填进去
}

void HeapSort(SqList& H) {
    for (int i = H.length / 2; i > 0; --i) {
        HeapAdjust(H, i, H.length);
    }
    for (int i = H.length; i > 1; --i) {
        swap(H.r[1], H.r[i]);
        HeapAdjust(H, 1, i - 1); // 剩下的结点的有效下标是 1 到 i-1
    }
}

归并排序

2-路归并排序

思路

将两个有序表合并成一个有序表。

严蔚敏数据结构伪代码

// 伪代码
void Msort(RedType SR[], RedType TR1[], int s, int t) {
    if (s == t) TR1[s] = SR[s];
    else {
        // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]
        int m = (s + t) / 2;
        // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]
        Msort(SR, TR2, s, m);
        // 递归地将 SR[m+1..t] 归并为有序的 TR2[m+1..t]
        Msort(SR, TR2, m + 1, t);
        // 将 TR2[s..m] 和 TR2[m+1..t] 归并到 TR1[s..t]
        // 课本是这样的，但是和下面的参数不对应
        Merge(TR2, TR1, s, m, t);
    }
}

void Merge(RecordType r1[], int low, int mid, int high, RecordType r[]) {
    // 已知 r1[low..mid] 和 r1[mid+1..high] 分别按关键字有序排列，将它们合并成一个有序序列，存放在 r[low..high]
    int i = low;
    int j = mid + 1;
    int k = low;
    while ((i <= mid) && (j <= high)) {
        if (r1[i].key <= r1[j].key) {
            r[k] = r1[i];
            ++i;
        } else {
            r[k] = r1[j];
            ++j;
        }
        ++k;
    }
    while (i <= mid) {
        r[k] = r1[i];
        k++;
        i++;
    }
    while (j <= high) {
        r[k] = r1[i]; // 注意：此处原文可能有误，应为 r1[j]
        k++;
        j++;
    }
}