排序算法：速度、内存与稳定性的权衡

同学们好！今天我们来聊聊排序算法——这是计算机科学中最基础也最实用的技能之一。想象一下，老师要按考试成绩从高到低排列全班同学的名字，或者电商网站要按价格排序商品，背后都需要排序算法。但不同的排序算法有不同的“性格”：有的快但占内存多，有的省空间但遇到特殊数据会变慢，还有的能保持相等元素的原始顺序（即稳定性）。学会分析时间复杂度和空间复杂度，以及判断稳定性，能帮你选出最合适的“排序工具”，尤其是在处理大数据或需要多关键字排序时（比如先按姓名排序，再按年龄排序，稳定排序能保住姓名的顺序）。

一、排序算法基础概念

1.1 时间与空间复杂度

时间复杂度：衡量算法执行所需要的时间，通常用大O表示法（如 $O(n^2), O(n \log n)$ ）。可以理解为：数据量翻倍，算法需要多花多少时间？比如 $O(n^2)$ 表示数据量翻倍，时间变成4倍； $O(n \log n)$ 则只变成约2倍多一点。
空间复杂度：衡量算法执行时额外占用的内存空间（不含输入数据本身）。比如归并排序需要临时数组存数据，就是“空间换时间”；而冒泡排序几乎不用额外空间，是“原地排序”。
稳定性：如果两个相等的元素在排序前后的相对顺序保持不变，则该排序算法是稳定的；否则是不稳定的。举个例子：班级有两位同学都考了95分，小明（原来排在前面）和小红（原来排在后面）。如果稳定排序，结果里小明依然在小红前面；不稳定排序则可能交换他俩的位置。

1.2 为什么要关注稳定性？

在实际应用中，我们经常需要按多个关键字排序。例如，先按“姓名”排好，再按“年龄”排（年龄相同时保持姓名顺序）。如果第二次排序用的是不稳定算法，那么第一次排序的姓名顺序就可能被打乱。所以稳定排序能避免额外的数据移动，让多关键字排序变得更简单。想想看：你要给一箱苹果先按颜色分堆，再按大小排序——如果按大小排序时把颜色顺序搞乱了，你就得重新分颜色，多麻烦呀！

二、常见排序算法性能对照表

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	✔ 稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	✘ 不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	✔ 稳定
快速排序	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	$O(\log n)$ 递归栈	✘ 不稳定
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	✔ 稳定
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	✘ 不稳定

说明：最好时间复杂度指数据基本有序时的情况（比如本来就想排好的数据，再排一次）；最坏指数据完全逆序或特殊分布（比如快速排序每次选到最小/最大元素）。

三、基于分治思想的核心算法详解

分治思想：把大问题分成几个小问题，分别解决，再合并结果。快速排序和归并排序都是典型代表。

3.1 快速排序（Quick Sort）

原理

选择一个基准元素（pivot），通常是数组的第一个或最后一个元素。
通过一趟扫描，将数组分为两部分：左边所有元素 ≤ pivot，右边所有元素 ≥ pivot。
对左右两部分递归地执行上述过程。

生活例子：想象你在整理一摞试卷，先随机抽出一张作为“标准线”，然后把所有比它分数低的放左边，高的放右边。接着对左边和右边的两堆分别重复这个操作，直到每堆只剩一张试卷。这样整个顺序就排好了。

示例代码（C++）

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

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选最后一个元素作为基准
    int i = low - 1;       // i 记录小于 pivot 的边界

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 将 pivot 放到正确位置
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

复杂度分析

时间复杂度：
- 平均： $O(n \log n)$ —— 每次划分大致平衡。
- 最坏： $O(n^2)$ —— 每次选到最小或最大元素（如已有序数组且固定选末尾）。这就像你每次抽到的标准线都是最高分或最低分，导致一边总是空堆，另一边全是剩下的，效率就很差。
空间复杂度：递归栈深度平均 $O(\log n)$ ，最坏 $O(n)$ （相当于递归了一长串）。
稳定性：不稳定 —— 交换操作可能打乱相等元素的相对顺序（如 pivot 与相等元素交换）。例如数组 [5a, 5b, 3]，基准选最后一个3，第一次交换会把5a和5b的顺序弄乱。

新手常见错误

基准选择不当导致最坏情况：如果数据已经有序，而你又固定选第一个或最后一个作基准，快排就退化成 $O(n^2)$ 。改进方法：随机选基准或“三数取中”。
递归边界问题：忘记判断 low < high 会导致无限递归。
分区时索引越界：指针 i 和 j 的移动要小心，特别是当所有元素都小于或都大于 pivot 时。

完整可运行示例（含主函数）

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

// 分区函数
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准选最后一个元素
    int i = low - 1;       // i指向小于基准区的最后一个位置

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 把基准放到正确位置
    return i + 1;
}

// 快速排序递归函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 获取基准最终位置
        quickSort(arr, low, pi - 1);        // 排左边
        quickSort(arr, pi + 1, high);       // 排右边
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    // 测试数组：包含重复元素，方便观察稳定性
    vector<int> arr = {8, 3, 5, 9, 5, 2, 7};
    cout << "原始数组: ";
    printArray(arr);

    quickSort(arr, 0, arr.size() - 1);

    cout << "排序后: ";
    printArray(arr);

    return 0;
}

3.2 归并排序（Merge Sort）

原理

将数组递归地分成两半，直到每部分只有一个元素。
将两个有序的子数组合并成一个有序数组（通过双指针比较）。

生活例子：老师让你把两堆按大小已排好的练习册合并成一堆。你只要分别看两堆最上面的那本，哪本小就拿哪本放到新堆里，重复直到全部拿完。这就是归并的“双指针合并”。而“分”的过程就像把一大叠纸不断对半裁开，直到每张都是一个单独的纸片。

示例代码（C++）

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

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    vector<int> L(n1), R(n2); // 创建临时数组存放左、右子数组

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    // 双指针合并
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {      // 注意：用 <= 保证稳定性（相等时先取左边的）
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    // 把剩余元素拷贝回去
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 防溢出写法
        mergeSort(arr, left, mid);           // 排左边
        mergeSort(arr, mid + 1, right);      // 排右边
        merge(arr, left, mid, right);        // 合并两个有序部分
    }
}

复杂度分析

时间复杂度：始终 $O(n \log n)$ —— 无论数据分布如何，递归深度 $\log n$ ，每层合并 $O(n)$ 。
空间复杂度： $O(n)$ —— 需要临时数组存储合并结果（递归栈 $O(\log n)$ 通常不计入主要空间）。
稳定性：稳定 —— 合并时当左右相等时，优先取左半部分，保证相等元素的原始顺序。

新手常见错误

忘记释放临时数组内存：用 vector 会自动管理，但用 new 分配的数组必须手动 delete（不过C++中建议直接用 vector）。
合并时索引错误：拷贝剩余元素时注意循环条件，很容易漏掉一部分。
递归基准错误：if (left < right) 中的 < 不能写成 <=，否则会无限递归。

完整可运行示例（含主函数）

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

// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;   // 左半部分长度
    int n2 = right - mid;      // 右半部分长度
    vector<int> L(n1), R(n2);  // 创建临时数组

    // 拷贝数据
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    // 双指针合并
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {      // 稳定：相等时先放左边的
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    // 拷贝剩余
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// 归并排序递归
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void printArray(const vector<int>& arr) {
    for (int val : arr) cout << val << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {8, 3, 5, 9, 5, 2, 7};
    cout << "原始数组: ";
    printArray(arr);

    mergeSort(arr, 0, arr.size() - 1);

    cout << "排序后: ";
    printArray(arr);

    return 0;
}

四、其他典型排序（非分治）简要分析

4.1 冒泡排序

原理：相邻元素两两比较，较大的后移，每轮将最大值“冒泡”到最后。
复杂度：平均/最坏 $O(n^2)$ ，最好 $O(n)$ （已有序时加标志位提前结束）。
空间： $O(1)$ 。
稳定性：稳定（相等元素不交换）。

例子：像水里的气泡一样，大的慢慢浮上去。生活中整理书架时，可以依次比较相邻两本书的序号，把大的往后挪。

4.2 选择排序

原理：每轮选出未排序部分的最小值，放到已排序末尾。
复杂度：始终 $O(n^2)$ 。
空间： $O(1)$ 。
稳定性：不稳定（例如 [5a, 5b, 3] => 第一次选3与5a交换，打破顺序）。

例子：每次从一堆牌里找出最小的牌放到手里最前面，但由于交换的是位置，可能打乱原先相等的牌的顺序。

4.3 插入排序

原理：将未排序元素插入到已排序部分的正确位置。
复杂度：最坏 $O(n^2)$ ，最好 $O(n)$ （已有序）。
空间： $O(1)$ 。
稳定性：稳定（相等时插入到后面）。

例子：打扑克牌时，你手头已经排好了一些牌，新摸到一张牌就找到合适位置插进去。所以相等牌会保持原来的前后顺序。

4.4 堆排序

原理：利用最大堆（或最小堆）不断取出堆顶元素。
复杂度：始终 $O(n \log n)$ 。
空间： $O(1)$ 。
稳定性：不稳定（建堆和交换时可能改变相同元素顺序）。

例子：像组织一场“淘汰赛”，每次从队伍里选出最大（或最小）的人放到结果里，但由于堆的调整会改变相对位置。

五、选择排序算法的建议

应用场景	推荐算法	原因
数据量小（<100）	插入排序	简单稳定，最好情况快
数据基本有序	插入排序 / 冒泡排序	最好时间复杂度 $O(n)$
数据量大，不要求稳定	快速排序（平均快）	通常效率最高
数据量大，要求稳定	归并排序	稳定且 $O(n \log n)$
内存受限（嵌入式）	堆排序	空间 $O(1)$
需要稳定且内存大	归并排序	稳定，但需额外空间

六、小结

分治排序（快排、归并）是五级考试的重点，需理解递归划分和合并过程。
稳定性判断技巧：具有“相邻交换”特性的算法通常稳定（冒泡、插入、归并）；“远距离交换”通常不稳定（选择、快排、堆排）。
空间复杂度尤其注意递归算法隐含的栈空间开销。

关键记忆：归并排序是用空间换时间的稳定排序；快速排序是平均性能最佳的原地排序。

常见排序的时间复杂度与空间复杂度与稳定性

排序算法：速度、内存与稳定性的权衡

一、排序算法基础概念

1.1 时间与空间复杂度

1.2 为什么要关注稳定性？

二、常见排序算法性能对照表

三、基于分治思想的核心算法详解

3.1 快速排序（Quick Sort）

原理

示例代码（C++）

复杂度分析

新手常见错误

完整可运行示例（含主函数）

3.2 归并排序（Merge Sort）

原理

示例代码（C++）

复杂度分析

新手常见错误

完整可运行示例（含主函数）

四、其他典型排序（非分治）简要分析

4.1 冒泡排序

4.2 选择排序

4.3 插入排序

4.4 堆排序

五、选择排序算法的建议

六、小结

相关指引