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

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

#include <iostream>
#include <stack>
#include <string>
#include <random>
using namespace std;
#define MAXSIZE 20
// 顺序表的长度
typedef int KeyType;
typedef string InfoType;

// 关键字类型为整数类型
typedef struct {
    KeyType key; // 关键字项
    InfoType otherinfo; // 其它数据项
} RedType; // 记录类型

typedef struct {
    RedType r[MAXSIZE + 1]; // r[0] 空作为哨兵
    int length; // 顺序表长度
} SqList; // 顺序表类型

// 打印函数
void PrintList(const SqList& L) {
    cout << "length = " << L.length << endl;
    for (int i = 1; i <= L.length; ++i) {
        cout << L.r[i].key << ", ";
    }
    cout << endl;
}

// 随机生成器
void InitRandomList(SqList& L, int n) {
    if (n > MAXSIZE) n = MAXSIZE;
    L.length = n;
    // 随机数引擎（高质量）
    static std::mt19937 gen(std::random_device{}());
    std::uniform_int_distribution<int> dist(0, 99);
    for (int i = 1; i <= n; ++i) {
        L.r[i].key = dist(gen);
        L.r[i].otherinfo = "info_" + to_string(i);
    }
}

//=====================================
// 直接插入排序
//=====================================
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];
        }
    }
}

//=====================================
// 折半查找插入排序
//=====================================
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);
}

//=========栈版本=========
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});
        }
    }
}

//=========随机选择枢纽版本=========
// 这个函数只负责选枢纽，并把它换到 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);
}

//=========三数取中版本=========
// 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);
}

// =====================================
// 简单选择排序
// =====================================
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;
}

// =====================================
// 堆排序
// =====================================
// 大顶堆
// 自顶到底重新堆化
// 下标从 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);
    }
}

维度	`swap` 交换法 )	`rc` 覆盖法 (严蔚敏版/当前代码)
操作本质	真的在内存里交换两个数	单向赋值，只移动数据，不交换
赋值次数	每次下沉需 3 次赋值	每次下沉需 1 次赋值

// 严蔚敏数据结构
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
    }
}

// 伪代码
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++;
    }
}

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

分类

按待排序记录所在位置

按排序依据原则

存储结构

插入排序

直接插入排序

思路

代码

折半查找插入排序

思路

代码

希尔排序

思路

代码

交换排序

冒泡排序

思路

代码

快速排序

思路

严蔚敏数据结构版本

优化 1：用栈模拟递归

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

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

选择排序

简单选择排序

思路

代码

树形选择排序

思路

代码

堆排序

思路

vector 版本

严蔚敏数据结构版本

归并排序

2-路归并排序

思路

严蔚敏数据结构伪代码

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

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

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