C++秋招必知必会（常用排序算法）

参考引用

Hello 算法

常用排序算法

在这里插入图片描述

1. 选择排序

1.1 算法原理与流程

开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾
设数组的长度为 $n$ ，选择排序的算法流程如下图
- 初始状态下，所有元素未排序，即未排序（索引）区间为 $[0, n - 1]$
- 选取区间 $[0, n - 1]$ 中的最小元素，将其与索引 $0$ 处元素交换。完成后，数组前 $1$ 个元素已排序
- 选取区间 $[1, n - 1]$ 中的最小元素，将其与索引 $1$ 处元素交换。完成后，数组前 $2$ 个元素已排序
- 以此类推。经过 $n - 1$ 轮选择与交换后，数组前 $n - 1$ 个元素已排序
- 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成

1.2 算法实现

时间复杂度（非自适应排序） $O(n^2)$
- 外循环共 $n - 1$ 轮，第一轮的未排序区间长度为 $n$ ，最后一轮的未排序区间长度为 $2$ ，即各轮外循环分别包含 $n 、 n - 1 、 ... 、 3 、 2$ 轮内循环，求和为 $\frac{(n-1)(n+2)}2$
空间复杂度（原地排序） $O (1)$
- 指针 i 和 j 使用常数大小的额外空间
非稳定排序：元素 nums[i] 有可能被交换至与其相等的元素的右边，导致两者的相对顺序发生改变

#include <iostream>
#include <vector>

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

/* 选择排序 */
void selectionSort(std::vector<int> &nums) {
    int n = nums.size();
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素索引
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex])
                minIndex = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        swap(nums[i], nums[minIndex]);
    }
}

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 3};
    
    std::cout << "Original array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    selectionSort(nums);
    
    std::cout << "Sorted array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

2. 冒泡排序

2.1 算法原理与流程

冒泡排序通过连续地比较与交换相邻元素实现排序，利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果 “左元素 > 右元素” 就交换二者，遍历完成后，最大的元素会被移动到数组的最右端
设数组的长度为 $n$ ，冒泡排序的步骤如下图
- 1、首先，对 $n$ 个元素执行 “冒泡”，将数组的最大元素交换至正确位置
- 2、接下来，对剩余 $n - 1$ 个元素执行 “冒泡”，将第二大元素交换至正确位置
- 3、以此类推，经过 $n - 1$ 轮 “冒泡” 后，前 $n - 1$ 大的元素都被交换至正确位置
- 4、仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成

2.2 算法实现

时间复杂度（自适应排序） $O(n^2)$
- 各轮 “冒泡” 遍历的数组长度依次为 $n - 1 、 n - 2 、 ...2 、 1$ ，总和 $\frac{(n-1)n}2$
- 输入数组完全有序时，可达最佳时间复杂度 $O (n)$
空间复杂度（原地排序） $O (1)$
- 指针 i 和 j 使用常数大小的额外空间
稳定排序：由于在 “冒泡” 中遇到相等元素不交换

#include <iostream>
#include <vector>

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

void bubbleSort(std::vector<int> &nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.size() - 1; i > 0; i--) {
        bool flag = false; // 初始化标志位
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                swap(nums[j], nums[j + 1]);
                flag = true; // 记录交换元素
            }
        }
        if (!flag)
            break; // 此轮“冒泡”未交换任何元素，直接跳出
    }
}

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 3};
    
    std::cout << "Original array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    bubbleSort(nums);
    
    std::cout << "Sorted array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

3. 插入排序

3.1 算法原理与流程

插入排序的工作原理
- 在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置，设基准元素为 base，需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引
插入排序的整体流程
- 初始状态下，数组的第 $1$ 个元素已完成排序
- 选取数组的第 $2$ 个元素作为 base，将其插入到正确位置后，数组的前 $2$ 个元素已排序
- 选取第 $3$ 个元素作为 base，将其插入到正确位置后，数组的前 $3$ 个元素已排序
- 以此类推，在最后一轮中，选取最后一个元素作为 base，将其插入到正确位置后，所有元素均已排序

3.2 算法实现

时间复杂度（自适应排序） $O(n^2)$
- 每次插入操作分别需要循环 $n - 1 、 n - 2 、 ...2 、 1$ ，总和 $\frac{(n-1)n}2$
- 遇到有序数据时，插入操作会提前终止，当输入数组完全有序时，插入排序最佳时间复杂度 $O (n)$
空间复杂度（原地排序） $O (1)$
- 指针 i 和 j 使用常数大小的额外空间
稳定排序：插入过程中会将元素插入到相等元素的右侧，不会改变它们的顺序

#include <iostream>
#include <vector>

void insertionSort(std::vector<int> &nums) {
    // 外循环：已排序元素数量为 1, 2, ..., n
    for (int i = 1; i < nums.size(); i++) {
        int base = nums[i];
        int j = i - 1;
        // 内循环：将 base 插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
            j--;
        }
        // j 已在上面 while 循环中 j--，故此处为 j + 1 
        nums[j + 1] = base; // 将 base 赋值到正确位置
    }
}

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 3};
    
    std::cout << "Original array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    insertionSort(nums);
    
    std::cout << "Sorted array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

插入排序的使用频率显著高于冒泡排序和选择排序

冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高
选择排序在任何情况下的时间复杂度都为 $O(n^2)$ 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高

4. 快速排序

4.1 算法原理与流程

快速排序是一种基于分治策略的排序算法，核心操作是 “哨兵划分”，其目标是：选择数组中的某个元素作为 “基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧
哨兵划分的流程
- 1、选取数组最左端元素作为基准数，初始化两个指针 $i$ 和 $j$ 分别指向数组的两端
- 2、设置两个循环，从右向左找首个小于基准数的元素，从左向右找首个大于基准数的元素，然后交换这两个元素
- 3、循环执行步骤 2，直到 $i$ 和 $j$ 相遇时停止，最后将基准数交换至两个子数组的分界线
- 哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足 “左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”，哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题

在这里插入图片描述

快速排序的整体流程
- 首先，对原数组执行一次 “哨兵划分”，得到未排序的左子数组和右子数组
- 然后，对左子数组和右子数组分别递归执行 “哨兵划分”
- 持续递归，直至子数组长度为 $1$ 时终止，从而完成整个数组的排序
递归：通过重复将问题分解为同类的子问题而解决问题的方法

在这里插入图片描述

4.2 算法实现

时间复杂度（自适应排序） $O (n l o g n)$
- 在平均情况下，哨兵划分的递归层数为 $l o g n$ ，每层中的总循环数为 $n$ ，总体使用 $O (n l o g n)$ 时间
- 在最差情况下，每轮哨兵划分操作都将长度为 $n$ 的数组划分为长度为 $0$ 和 $n - 1$ 的两个子数组，此时递归层数达到 $n$ ，每层中的循环数为 $n$ ，总体使用 $O(n^2)$ 时间
空间复杂度（原地排序） $O (n)$
- 在输入数组完全倒序的情况下，达到最差递归深度 $n$ ，使用 $O (n)$ 栈帧空间
- 排序操作是在原数组上进行的，未借助额外数组
非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧

#include <iostream>
#include <vector>

/* 元素交换 */
void swap(std::vector<int> &nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 哨兵划分 */
int partition(std::vector<int> &nums, int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--; // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 从左向右找首个大于基准数的元素
        swap(nums, i, j); // 交换这两个元素
    }
    swap(nums, i, left); // 将基准数交换至两子数组的分界线
    return i;            // 返回基准数的索引
}

/* 快速排序 */
void quickSort(std::vector<int> &nums, int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right)
        return;
    // 哨兵划分
    int pivot = partition(nums, left, right);
    // 递归左子数组、右子数组
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 3};
    
    std::cout << "Original array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    quickSort(nums, 0, nums.size() - 1);
    
    std::cout << "Sorted array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

快速排序为什么快？
- 出现最差情况的概率很低
  - 虽然快速排序的最差时间复杂度为 $O(n^2)$ ，没有归并排序稳定，但绝大多数情况下，快速排序能在 $O (n l o g n)$ 的时间复杂度下运行
- 缓存使用效率高
  - 在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高，而堆排序需要跳跃式访问元素，从而缺乏这一特性
- 复杂度的常数系数小
  - 在上述三种分治排序算法中（快速、归并、堆排序），快速排序的比较、赋值、交换等操作的总数量最少，这与 “插入排序” 比 “冒泡排序” 更快的原因类似

5. 归并排序

5.1 算法原理与流程

归并排序是一种基于分治策略的排序算法，包含 “划分” 和 “合并” 阶段
- “划分阶段” 从顶至底递归地将数组从中点切分为两个子数组
  - 1、计算数组中点 mid ，递归划分左子数组（区间 [left, mid] ）和右子数组（区间 [mid + 1, right] ）
  - 2、递归执行步骤 1，直至子数组区间长度为 1 时终止
- “合并阶段” 从底至顶地将左子数组和右子数组合并为一个有序数组
  - 从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的

5.2 算法实现

时间复杂度（非自适应排序） $O (n l o g n)$
- 划分产生高度为 $l o g n$ 的递归树，每层合并的总操作数量为 $n$ ，因此总体时间复杂度为 $O (n l o g n)$
空间复杂度（非原地排序） $O (n)$
- 递归深度为 $l o g n$ ，使用 $O (l o g n)$ 大小的栈帧空间。合并操作需要借助辅助数组实现，使用 $O (n)$ 大小的额外空间
稳定排序：在合并过程中，相等元素的次序保持不变

#include <iostream>
#include <vector>

/* 合并左子数组和右子数组 */
void merge(std::vector<int> &nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    std::vector<int> tmp(right - left + 1);
    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmp.size(); k++) {
        nums[left + k] = tmp[k];
    }
}

/* 归并排序 */
void mergeSort(std::vector<int> &nums, int left, int right) {
    // 终止条件
    if (left >= right)
        return; // 当子数组长度为 1 时终止递归
    // 划分阶段
    int mid = (left + right) / 2;    // 计算中点
    mergeSort(nums, left, mid);      // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并阶段
    merge(nums, left, mid, right);
}

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 3};
    
    std::cout << "Original array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    mergeSort(nums, 0, nums.size() - 1);
    
    std::cout << "Sorted array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

6. 堆排序

6.1 算法原理与流程

堆排序是一种基于堆数据结构实现的分治策略排序算法
设数组的长度为 $n$ ，堆排序的流程如下
- 1、输入数组并建立大顶堆。完成后，最大元素位于堆顶
- 2、将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 $1$ ，已排序元素数量加 $1$
- 3、从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复
- 4、循环执行第 2 步和第 3 步。循环 $n - 1$ 轮后，即可完成数组排序

6.2 算法实现

时间复杂度（非自适应排序） $O (n l o g n)$
- 建堆操作使用 $O (n)$ 时间，从堆中提取最大元素的时间复杂度为 $O (l o g n)$ ，共循环 $n - 1$ 轮
空间复杂度（原地排序） $O (1)$
- 几个指针变量使用 $O(1) 空间，元素交换和堆化操作都是在原数组上进行的
非稳定排序：在交换堆顶元素和堆底元素时，相等元素的相对位置可能发生变化

#include <iostream>
#include <vector>

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(std::vector<int> &nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) {
            break;
        }
        // 交换两节点
        swap(nums[i], nums[ma]);
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(std::vector<int> &nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.size() / 2 - 1; i >= 0; --i) {
        siftDown(nums, nums.size(), i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.size() - 1; i > 0; --i) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        swap(nums[0], nums[i]);
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 3};
    
    std::cout << "Original array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    heapSort(nums);
    
    std::cout << "Sorted array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

7. 桶排序

7.1 算法原理与流程

桶排序是分治策略的一个典型应用，原理如下
- 通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中
- 然后，在每个桶内部分别执行排序
- 最终按照桶的顺序将所有数据合并
考虑一个长度为 $n$ 的数组，其元素是范围 $[0, 1)$ 内的浮点数，桶排序的流程如下
- 初始化 $k$ 个桶，将 $n$ 个元素分配到 $k$ 个桶中
- 对每个桶分别执行排序
- 按照桶从小到大的顺序合并结果

7.2 算法实现

桶排序适用于处理体量很大的数据如：输入数据包含 100 万个元素，由于空间限制，系统内存无法一次性加载所有数据。此时，可以将数据分成 1000 个桶，然后分别对每个桶进行排序，最后将结果合并
- 时间复杂度 $O (n + k)$ ：假设元素在各个桶内平均分布，那么每个桶内的元素数量为 $\frac{n}{k}$ 。假设排序单个桶使用 $O(\frac{\mathrm{n}}{k}\log\frac{\mathrm{n}}{k})$ 时间，则排序所有桶使用 $O(n\log{\frac{n}{k}})$ 时间。当桶数量 $k$ 比较大时，时间复杂度则趋向于 $O (n)$ 。合并结果时需要遍历所有桶和元素，花费 $O (n + k)$ 时间
- 自适应排序：在最差情况下，所有数据被分配到一个桶中，且排序该桶使用 $O(n^2)$ 时间
- 空间复杂度（非原地排序） $O (n + k)$ ：需要借助 $k$ 个桶和总共 $n$ 个元素的额外空间
桶排序是否稳定取决于排序桶内元素的算法是否稳定

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<float>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                float temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

/* 桶排序 */
void bucketSort(vector<float> &nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.size() / 2;
    vector<vector<float>> buckets(k);
    // 1. 将数组元素分配到各个桶中
    for (float num : nums) {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = num * k;
        // 将 num 添加进桶 bucket_idx
        buckets[i].push_back(num);
    }
    // 2. 对各个桶执行排序
    for (vector<float> &bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        bubbleSort(bucket); // 使用冒泡排序手动实现替代 std::sort
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (vector<float> &bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}

int main() {
    std::vector<float> nums = {0.8, 0.2, 0.3, 0.5, 0.1, 0.9, 0.7, 0.6, 0.4};
    
    cout << "Original array:" << endl;
    for (float num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    bucketSort(nums);
    
    cout << "Sorted array:" << endl;
    for (float num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}