排序算法

排序是面试基础题，重点不是背代码，而是说清每种算法的思想、复杂度、稳定性、原地性，以及工程中如何选择。

总览

算法	平均	最坏	最好	空间	稳定	原地
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	✅	✅
选择排序	O(n²)	O(n²)	O(n²)	O(1)	❌	✅
插入排序	O(n²)	O(n²)	O(n)	O(1)	✅	✅
希尔排序	取决于增量序列	取决于增量序列，常见上界 O(n²)	取决于增量序列	O(1)	❌	✅
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✅	❌
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n) 栈	❌	✅
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	❌	✅
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	✅	❌
基数排序	O(d·(n+k))	O(d·(n+k))	O(d·(n+k))	O(n+k)	✅	❌
桶排序	O(n + k)	O(n²)	O(n)	O(n)	✅	❌

稳定性：相等元素的相对顺序是否保持。原地性：是否只需 O(1) 额外空间。

O(n²) 简单排序

冒泡排序

相邻元素两两比较，大的向后冒。每轮至少把一个最大值放到正确位置。若某一轮无交换说明已有序，可提前退出（最好 O(n)）。

void bubble_sort(std::vector<int>& nums) {
    const int n = static_cast<int>(nums.size());
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (nums[j] > nums[j + 1]) {
                std::swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

选择排序

每轮从未排序部分选出最小值，放到已排序部分末尾。比较次数固定为 O(n²)，不稳定：例如 [5, 5, 3]，第一轮把 3 和第一个 5 交换，两个 5 的相对顺序就变了。

void selection_sort(std::vector<int>& nums) {
    const int n = static_cast<int>(nums.size());
    for (int i = 0; i < n - 1; ++i) {
        int min_index = i;
        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[min_index]) min_index = j;
        }
        std::swap(nums[i], nums[min_index]);
    }
}

插入排序

把当前元素插入到已排序前缀的正确位置。数据基本有序时接近 O(n)，是稳定的，且对"近乎有序"数据非常快，常作为快排/归并的递归终点优化。

void insertion_sort(std::vector<int>& nums) {
    const int n = static_cast<int>(nums.size());
    for (int i = 1; i < n; ++i) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            --j;
        }
        nums[j + 1] = key;
    }
}

希尔排序

插入排序的改进：按增量分组做插入排序，增量逐渐缩小到 1。利用“基本有序时插入快”的特性，但分组破坏了稳定性。希尔排序的时间复杂度高度依赖增量序列，不能脱离具体序列给出统一的平均或最坏界；简单增量序列的最坏情况可达 O(n²)。

O(n log n) 排序

归并排序

分治：把数组分成两半分别排序，再合并两个有序数组。合并需要 O(n) 辅助空间；稳定，性能不依赖输入分布（最好最坏都是 O(n log n)）。

void merge(std::vector<int>& nums, int left, int mid, int right) {
    std::vector<int> tmp(nums.begin() + left, nums.begin() + right + 1);
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (tmp[i - left] <= tmp[j - left]) nums[k++] = tmp[i++ - left];
        else nums[k++] = tmp[j++ - left];
    }
    while (i <= mid) nums[k++] = tmp[i++ - left];
    while (j <= right) nums[k++] = tmp[j++ - left];
}

void merge_sort(std::vector<int>& nums, int left, int right) {
    if (left >= right) return;
    const int mid = left + (right - left) / 2;
    merge_sort(nums, left, mid);
    merge_sort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

快速排序

分治：选 pivot，partition 使左边 ≤ pivot、右边 ≥ pivot，再递归两边。平均 O(n log n)，最坏 O(n²)（如已有序数组选到端点 pivot）。不稳定。

int partition(std::vector<int>& nums, int left, int right) {
    const int pivot = nums[right];
    int store = left;
    for (int i = left; i < right; ++i) {
        if (nums[i] <= pivot) std::swap(nums[store++], nums[i]);
    }
    std::swap(nums[store], nums[right]);
    return store;
}

void quick_sort(std::vector<int>& nums, int left, int right) {
    if (left >= right) return;
    const int p = partition(nums, left, right);
    quick_sort(nums, left, p - 1);
    quick_sort(nums, p + 1, right);
}

工程中常见的快速排序改进（许多标准库实现会采用其中一部分或内省排序变体，但这不是 C++ 标准的算法承诺）：

• 随机选 pivot：避免有序输入退化为 O(n²)；
• 三数取中：取 left、mid、right 的中位数作 pivot；
• 小数组用插入排序：递归到长度 ~16 时切到插入排序，减少函数调用；
• 三向切分：大量重复元素时，把等于 pivot 的部分放中间，两边只递归不等的部分。

这是常见**内省排序（introsort）**的思路：以快排的平均性能为主，在深度异常时用堆排序防止最坏 O(n²)，小区间用插入排序降低常数。

堆排序

利用最大堆：先 make_heap（O(n)），反复把堆顶与末尾交换并缩小堆范围下沉。不稳定、原地，但实际常数较大且缓存不友好，工程上慢于快排/归并。实现见 堆与优先队列 的 pop 思路。

线性排序：突破 O(n log n)

比较排序的下界是 Ω(n log n)（决策树证明）。要更快必须利用数据特征，不通过比较。

计数排序

值域有限且已知（如 0~k）：统计每个值出现次数，累加前缀和得到每个值的最终位置，从后往前填保证稳定。

基数排序

按位多次排序（个位、十位……），每轮用稳定排序（通常计数排序）。适合整数、字符串，d 位数字复杂度 O(d·(n+k))。

桶排序

把数据按范围分到若干桶，桶内排序（常插排），再按序拼接。数据均匀分布时接近 O(n)。

面试易错点

1. 快排最坏 O(n²) 不是"常数问题"，而是有序/逆序输入 + 固定 pivot 的必然结果；
2. 选择排序不稳定，冒泡/插入/归并稳定；希尔、快排、堆排不稳定；
3. 归并需要 O(n) 额外空间，快排需要 O(log n) 递归栈（最坏 O(n)）；
4. 比较排序最快 Ω(n log n)，想突破必须用非比较算法；
5. 标准只约束 std::sort 的复杂度与语义，不规定具体算法；常见实现采用内省排序（快排 + 堆排兜底 + 小区间插入排序）。std::stable_sort 保证稳定，常见实现基于归并，但同样不应把具体实现当作标准要求；
6. 写快排 partition 时注意 mid 计算用 left + (right - left) / 2 防溢出；
7. 堆排序交换堆顶后必须重新 sift_down，否则堆序被破坏。

关联笔记

• 堆与优先队列
• 数组、前缀和与区间
• 二分查找