1. 1. 排序算法总结（C++版）
  2. 2. 一、总览
  3. 3. 二、冒泡排序
    1. 3.1. 1. 思想
    2. 3.2. 2. 例子
    3. 3.3. 3. 代码
    4. 3.4. 4. 特点
    5. 3.5. 5. 高频追问
      1. 3.5.1. 为什么稳定？
  4. 4. 三、选择排序
    1. 4.1. 1. 思想
    2. 4.2. 2. 代码
    3. 4.3. 3. 特点
    4. 4.4. 4. 为什么不稳定？
  5. 5. 四、插入排序
    1. 5.1. 1. 思想
    2. 5.2. 2. 例子
    3. 5.3. 3. 代码
    4. 5.4. 4. 特点
    5. 5.5. 5. 高频追问
      1. 5.5.1. 为什么很多库排序在小区间会退化成插入排序？
  6. 6. 五、希尔排序
    1. 6.1. 1. 思想
    2. 6.2. 2. 代码
    3. 6.3. 3. 特点
  7. 7. 六、归并排序
    1. 7.1. 1. 思想
    2. 7.2. 2. 代码
    3. 7.3. 3. 特点
    4. 7.4. 4. 高频追问
      1. 7.4.1. 为什么归并排序是稳定的？
      2. 7.4.2. 为什么适合链表排序？
  8. 8. 七、快速排序
    1. 8.1. 1. 思想
    2. 8.2. 2. 经典模板
    3. 8.3. 3. 特点
    4. 8.4. 4. 高频追问
      1. 8.4.1. 为什么先走右边再走左边？
      2. 8.4.2. 为什么要随机 pivot？
      3. 8.4.3. 快排为什么平均是 O(n log n)？
  9. 9. 八、快速选择（Quick Select）
    1. 9.1. 1. 适用题型
    2. 9.2. 2. 思想
    3. 9.3. 3. 复杂度
    4. 9.4. 4. 典型题
  10. 10. 九、堆排序
    1. 10.1. 1. 思想
    2. 10.2. 2. 代码
    3. 10.3. 3. 特点
    4. 10.4. 4. 高频追问
      1. 10.4.1. 为什么建堆从 n/2 - 1 开始？
      2. 10.4.2. 为什么堆排序不稳定？
      3. 10.4.3. 数组中如何表示堆？
  11. 11. 十、计数排序
    1. 11.1. 1. 思想
    2. 11.2. 2. 代码
    3. 11.3. 3. 特点
    4. 11.4. 4. 高频追问
      1. 11.4.1. 为什么计数排序不适合数据范围特别大？
  12. 12. 十一、桶排序
    1. 12.1. 1. 思想
    2. 12.2. 2. 特点
    3. 12.3. 3. 高频追问
      1. 12.3.1. 桶排序和计数排序区别？
  13. 13. 十二、基数排序
    1. 13.1. 1. 思想
    2. 13.2. 2. 特点
    3. 13.3. 3. 高频追问
      1. 13.3.1. 为什么基数排序要求子排序稳定？
  14. 14. 十三、稳定排序与不稳定排序
    1. 14.1. 1. 什么叫稳定？
    2. 14.2. 2. 常见稳定排序
    3. 14.3. 3. 常见不稳定排序
  15. 15. 十四、面试最常考的几个对比
    1. 15.1. 1. 快排 vs 归并
      1. 15.1.1. 快排
      2. 15.1.2. 归并
    2. 15.2. 2. 快排 vs 堆排
      1. 15.2.1. 快排
      2. 15.2.2. 堆排
    3. 15.3. 3. 插入排序 vs 冒泡排序
  16. 16. 十五、面试中排序题怎么选
    1. 16.1. 1. 如果题目就是“排序数组”
    2. 16.2. 2. 如果是链表排序
    3. 16.3. 3. 如果是找第 K 大/第 K 小
    4. 16.4. 4. 如果数据范围特别小，而且是整数
    5. 16.5. 5. 如果数组很小或接近有序
  17. 17. 十六、面试中常见问题整理
    1. 17.1. 1. 哪些排序是 O(n log n)？
    2. 17.2. 2. 哪些排序是稳定的？
    3. 17.3. 3. 哪些排序是原地排序？
    4. 17.4. 4. 为什么快排平均快？
    5. 17.5. 5. 为什么归并适合外部排序？
    6. 17.6. 6. 堆排序为什么空间复杂度 O(1)？
  18. 18. 十七、最建议背的三个模板
    1. 18.1. 1. 快排
    2. 18.2. 2. 归并
    3. 18.3. 3. 堆排
  19. 19. 十八、最后总结
    1. 19.1. 第一优先级
    2. 19.2. 第二优先级
    3. 19.3. 第三优先级
  20. 20. 十九、附：一句话背诵版

排序算法总结

c++ › 随笔

排序算法总结（C++版）

这篇文章把面试里最常考的排序算法做一个系统整理。目标不是只会背结论，而是能在面试里把：

  • 核心思想
  • 时间复杂度
  • 空间复杂度
  • 稳定性
  • 适用场景
  • 手写模板
  • 高频追问

说清楚。

一、总览

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 特点
冒泡排序 O(n^2) O(n^2) O(1) 稳定 简单，适合入门
选择排序 O(n^2) O(n^2) O(1) 不稳定 交换次数少
插入排序 O(n^2) O(n^2) O(1) 稳定 小规模数据很好用
希尔排序 约 O(n^1.3 ~ n^2) O(n^2) O(1) 不稳定 插入排序的优化版
归并排序 O(n log n) O(n log n) O(n) 稳定 分治思想，复杂度稳定
快速排序 O(n log n) O(n^2) O(log n) 不稳定 面试最常考，实际常很快
堆排序 O(n log n) O(n log n) O(1) 不稳定 原地排序，复杂度稳定
计数排序 O(n + k) O(n + k) O(k) 稳定 适合数据范围小的整数
桶排序 近似 O(n) 取决于分布 取决于桶数 可稳定 适合分布均匀的数据
基数排序 O(d(n + k)) O(d(n + k)) O(n + k) 稳定 适合位数固定的整数/字符串

二、冒泡排序

1. 思想

相邻两个元素两两比较，如果顺序不对就交换。每一轮会把当前最大的元素“冒泡”到最后。

2. 例子

数组：

1
[5, 2, 3, 1]

第一轮：

  • 5 和 2 比，交换 -> [2,5,3,1]
  • 5 和 3 比，交换 -> [2,3,5,1]
  • 5 和 1 比，交换 -> [2,3,1,5]

这一轮结束，最大值 5 到末尾。

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSort(vector<int>& nums) {
    int n = 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]) {
                swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

4. 特点

  • 稳定排序
  • 空间 O(1)
  • 优化后，如果数组本来就有序，可以提前结束

5. 高频追问

为什么稳定？

因为只有前一个元素严格大于后一个元素时才交换，相等元素不会改变相对顺序。

三、选择排序

1. 思想

每一轮从未排序部分中找最小值，放到当前起始位置。

2. 代码

1
2
3
4
5
6
7
8
9
10
11
12
void selectionSort(vector<int>& nums) {
    int n = nums.size();
    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;
            }
        }
        if (minIndex != i) swap(nums[i], nums[minIndex]);
    }
}

3. 特点

  • 不稳定
  • 空间 O(1)
  • 交换次数少，但比较次数固定很多

4. 为什么不稳定？

例如：

1
[5a, 5b, 3]

第一轮会把 3 交换到最前面，可能变成：

1
[3, 5b, 5a]

相等元素 5a 和 5b 的顺序变了，所以不稳定。

四、插入排序

1. 思想

把数组分成“已排序区间”和“未排序区间”，每次从未排序区间拿一个数，插到已排序区间正确位置。

2. 例子

1
[5, 2, 3, 1]
  • 先认为 5 已有序
  • 插入 2 -> [2,5,3,1]
  • 插入 3 -> [2,3,5,1]
  • 插入 1 -> [1,2,3,5]

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(vector<int>& nums) {
    int n = 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;
    }
}

4. 特点

  • 稳定
  • 空间 O(1)
  • 对“小规模”或“接近有序”的数据非常好

5. 高频追问

为什么很多库排序在小区间会退化成插入排序？

因为插入排序常数小、实现简单，对小数组往往比快排、归并更快。

五、希尔排序

1. 思想

希尔排序本质上是“分组插入排序”。

先按 gap 把相距较远的元素看成一组，分别做插入排序；再不断缩小 gap，最后 gap = 1 时，相当于做一次整体插入排序。

2. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shellSort(vector<int>& nums) {
    int n = nums.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = nums[i];
            int j = i - gap;
            while (j >= 0 && nums[j] > key) {
                nums[j + gap] = nums[j];
                j -= gap;
            }
            nums[j + gap] = key;
        }
    }
}

3. 特点

  • 不稳定
  • 是插入排序的优化版
  • 面试频率不如快排、归并、堆排高，但偶尔会问

六、归并排序

1. 思想

归并排序就是：

先递归拆分，再合并两个有序数组。

把数组不断拆成两半，直到每部分只有一个元素；然后再把两个有序子数组合并起来。

2. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void mergeSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);

    vector<int> tmp;
    int i = l, j = mid + 1;

    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp.push_back(nums[i++]);
        else tmp.push_back(nums[j++]);
    }
    while (i <= mid) tmp.push_back(nums[i++]);
    while (j <= r) tmp.push_back(nums[j++]);

    for (int k = 0; k < (int)tmp.size(); k++) {
        nums[l + k] = tmp[k];
    }
}

完整调用：

1
2
3
void sortArray(vector<int>& nums) {
    mergeSort(nums, 0, nums.size() - 1);
}

3. 特点

  • 时间复杂度稳定 O(n log n)
  • 稳定排序
  • 空间复杂度 O(n)

4. 高频追问

为什么归并排序是稳定的？

因为合并时如果相等，通常先放左边元素：

1
if (nums[i] <= nums[j])

这样相同元素的相对顺序不会变。

为什么适合链表排序？

链表不适合随机访问，但特别适合从中间断开再合并，所以链表排序经典就是归并排序。

七、快速排序

1. 思想

快速排序就是：

选一个 pivot，把小于等于它的放左边，大于等于它的放右边，然后递归排左右两边。

2. 经典模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;

    int p = l + rand() % (r - l + 1);
    swap(nums[l], nums[p]);

    int i = l, j = r;
    int pivot = nums[l];

    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        while (i < j && nums[i] <= pivot) i++;
        if (i < j) swap(nums[i], nums[j]);
    }

    nums[l] = nums[i];
    nums[i] = pivot;

    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

完整调用：

1
2
3
4
void sortArray(vector<int>& nums) {
    srand(time(0));
    quickSort(nums, 0, nums.size() - 1);
}

3. 特点

  • 平均 O(n log n)
  • 最坏 O(n^2)
  • 空间复杂度平均 O(log n)
  • 不稳定
  • 面试最常考

4. 高频追问

为什么先走右边再走左边？

因为 pivot 放在左边，最后要把坑位留给 pivot，常见模板就是先从右往左找小的，再从左往右找大的。

为什么要随机 pivot？

为了避免原数组接近有序时退化成 O(n^2)。

快排为什么平均是 O(n log n)？

每轮 partition 代价是 O(n)，平均情况下会比较均匀地分成两部分，所以递归层数平均是 O(log n)，总复杂度是 O(n log n)。

八、快速选择（Quick Select）

虽然它不是完整排序，但面试经常和快排一起问。

1. 适用题型

  • 第 K 大元素
  • 最小的 K 个数

2. 思想

它复用了快排的 partition，但不递归两边，只递归答案所在的一边。

3. 复杂度

  • 平均 O(n)
  • 最坏 O(n^2)

4. 典型题

  • LeetCode 215. 数组中的第 K 个最大元素

九、堆排序

1. 思想

堆排序可以理解成：

先建大根堆，再不断把堆顶最大值交换到数组末尾。

2. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void heapify(vector<int>& nums, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && nums[left] > nums[largest]) largest = left;
    if (right < n && nums[right] > nums[largest]) largest = right;

    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

void heapSort(vector<int>& nums) {
    int n = nums.size();

    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

3. 特点

  • O(n log n)
  • 空间 O(1)
  • 不稳定
  • 原地排序

4. 高频追问

为什么建堆从 n/2 - 1 开始？

因为叶子节点没有孩子，不需要向下调整。最后一个非叶子节点就是 n/2 - 1。

为什么堆排序不稳定？

因为堆顶和末尾交换时，相同元素的相对顺序可能被打乱。

数组中如何表示堆？

对于下标 i：

  • 左孩子：2*i + 1
  • 右孩子：2*i + 2
  • 父节点：(i - 1) / 2

十、计数排序

1. 思想

适用于数据范围不大的整数。统计每个数出现了多少次，然后按次数回填。

2. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> countingSort(vector<int>& nums) {
    int mn = *min_element(nums.begin(), nums.end());
    int mx = *max_element(nums.begin(), nums.end());
    vector<int> cnt(mx - mn + 1, 0);

    for (int x : nums) cnt[x - mn]++;

    vector<int> res;
    for (int i = 0; i < (int)cnt.size(); i++) {
        while (cnt[i]--) {
            res.push_back(i + mn);
        }
    }
    return res;
}

3. 特点

  • 时间复杂度 O(n + k)
  • 适合整数且范围小
  • 不是基于比较的排序

4. 高频追问

为什么计数排序不适合数据范围特别大？

因为需要开一个按值域大小分配的数组，值域太大会造成空间浪费甚至无法接受。

十一、桶排序

1. 思想

把数据分到多个桶里，每个桶内再单独排序，最后按桶顺序拼起来。

2. 特点

  • 适合数据分布比较均匀的情况
  • 如果分布很差，可能退化
  • 常作为思路题，不一定真让你手写完整版

3. 高频追问

桶排序和计数排序区别？

  • 计数排序是“每个值对应一个计数位”
  • 桶排序是“每个区间对应一个桶”

十二、基数排序

1. 思想

按位排序。常见是从个位开始，到十位、百位……每一位都做一次稳定排序。

2. 特点

  • 适合位数固定的整数或字符串
  • 依赖稳定排序作为子过程
  • 不是基于比较的排序

3. 高频追问

为什么基数排序要求子排序稳定？

因为低位排好的相对顺序，需要在更高位排序时保留下来。

十三、稳定排序与不稳定排序

1. 什么叫稳定？

如果两个元素值相同，排序后它们的相对顺序不变，就叫稳定排序。

例如：

1
[3a, 1, 3b]

如果排序后还是：

1
[1, 3a, 3b]

那就是稳定。

如果变成：

1
[1, 3b, 3a]

那就是不稳定。

2. 常见稳定排序

  • 冒泡排序
  • 插入排序
  • 归并排序
  • 计数排序
  • 基数排序

3. 常见不稳定排序

  • 选择排序
  • 快速排序
  • 堆排序
  • 希尔排序

十四、面试最常考的几个对比

1. 快排 vs 归并

快排

  • 平均 O(n log n)
  • 最坏 O(n^2)
  • 空间较省
  • 不稳定
  • 实际常很快

归并

  • 稳定 O(n log n)
  • 需要 O(n) 额外空间
  • 稳定排序
  • 适合链表排序和外部排序

2. 快排 vs 堆排

快排

  • 平均更快
  • 常数通常更优
  • 最坏会退化

堆排

  • 复杂度稳定 O(n log n)
  • 原地排序 O(1)
  • 但实际常数偏大，通常没快排快

3. 插入排序 vs 冒泡排序

  • 都是 O(n^2)
  • 但插入排序通常更常用、也更高效一点
  • 冒泡排序更多偏教学和基础题

十五、面试中排序题怎么选

1. 如果题目就是“排序数组”

优先考虑：

  • 快排
  • 归并排序
  • 堆排序

2. 如果是链表排序

优先：

  • 归并排序

3. 如果是找第 K 大/第 K 小

优先：

  • 快速选择
  • 堆

4. 如果数据范围特别小，而且是整数

优先考虑：

  • 计数排序
  • 基数排序

5. 如果数组很小或接近有序

优先考虑：

  • 插入排序

十六、面试中常见问题整理

1. 哪些排序是 O(n log n)？

常见比较排序里：

  • 归并排序
  • 快速排序（平均）
  • 堆排序

2. 哪些排序是稳定的？

  • 冒泡
  • 插入
  • 归并
  • 计数
  • 基数

3. 哪些排序是原地排序？

常见：

  • 冒泡
  • 选择
  • 插入
  • 希尔
  • 快排（通常算原地）
  • 堆排

归并排序一般不算原地，因为要额外数组。

4. 为什么快排平均快？

因为 partition 操作局部性好，常数小，而且不需要像归并那样额外开大数组。

5. 为什么归并适合外部排序？

因为它的“分块 + 合并”过程天然适合磁盘文件分段处理。

6. 堆排序为什么空间复杂度 O(1)？

因为它直接在原数组上建堆和调整，不需要额外的大数组。

十七、最建议背的三个模板

1. 快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;
    int p = l + rand() % (r - l + 1);
    swap(nums[l], nums[p]);

    int i = l, j = r, pivot = nums[l];
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        while (i < j && nums[i] <= pivot) i++;
        if (i < j) swap(nums[i], nums[j]);
    }
    nums[l] = nums[i];
    nums[i] = pivot;

    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

2. 归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void mergeSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);

    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp.push_back(nums[i++]);
        else tmp.push_back(nums[j++]);
    }
    while (i <= mid) tmp.push_back(nums[i++]);
    while (j <= r) tmp.push_back(nums[j++]);

    for (int k = 0; k < (int)tmp.size(); k++) {
        nums[l + k] = tmp[k];
    }
}

3. 堆排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void heapify(vector<int>& nums, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && nums[l] > nums[largest]) largest = l;
    if (r < n && nums[r] > nums[largest]) largest = r;

    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

void heapSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--) heapify(nums, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

十八、最后总结

如果从“面试最值得优先掌握”的角度看，建议这样记：

第一优先级

  • 快速排序
  • 归并排序
  • 堆排序

这三个最核心。

第二优先级

  • 插入排序
  • 冒泡排序
  • 选择排序

这几个用于补基础、讲稳定性、讲复杂度。

第三优先级

  • 计数排序
  • 桶排序
  • 基数排序

这几个偏“非比较排序”，常作为扩展和追问。

如果你只能背最少内容，那就至少把下面这些背熟：

  1. 快排模板 + 为什么随机 pivot
  2. 归并模板 + 为什么稳定
  3. 堆排模板 + 为什么从 n/2 - 1 开始建堆
  4. 稳定性表
  5. 各排序复杂度对比

这样大部分排序相关面试题都能覆盖。

十九、附：一句话背诵版

  • 冒泡：相邻比较，大的往后冒，稳定。
  • 选择：每轮选最小放前面，不稳定。
  • 插入：把当前元素插进前面有序区，稳定。
  • 希尔：分组做插入，逐步缩 gap，不稳定。
  • 归并：先分再并，复杂度稳定 O(n log n)，稳定。
  • 快排：选 pivot 分两边，平均 O(n log n)，不稳定。
  • 堆排：建大根堆，反复取堆顶，O(n log n)，不稳定。
  • 计数：统计次数后回填，适合小范围整数。
  • 桶排：按区间分桶，桶内再排，适合分布均匀。
  • 基数：按位稳定排序，适合位数固定的数据。