【数据结构与算法】第36篇：排序大总结：稳定性、时间复杂度与适用场景

目录

一、十大排序算法总览

二、稳定性详解

2.1 什么是稳定性

2.2 什么时候需要稳定性

2.3 各算法稳定性原因

三、时间复杂度分析

3.1 增长曲线对比

3.2 实际运行时间参考（n=50000随机数据）

四、空间复杂度分析

五、场景选型指南

5.1 数据规模小（n < 1000）

5.2 数据规模中等（1000 < n < 50000）

5.3 数据规模大（n > 50000）

5.4 特殊场景

六、混合排序（工业级实现）

七、面试高频考点

7.1 手写代码常考

7.2 概念常考

八、快速对比卡片

O(n²) 级（适合小数据）

O(n log n) 级（工业标准）

O(n) 级（特殊场景）

九、小结

十、思考题

一、十大排序算法总览

k表示数据范围（如计数排序中最大值与最小值的差），d表示位数（基数排序中）

二、稳定性详解

2.1 什么是稳定性

稳定排序：相等的元素在排序前后相对位置不变。

text

原数组：[(2,A), (1,B), (2,C)] // 数字为键，字母为附加信息 稳定排序后：[(1,B), (2,A), (2,C)] // 两个2的相对顺序不变 不稳定排序后：[(1,B), (2,C), (2,A)] // 顺序可能改变

2.2 什么时候需要稳定性

2.3 各算法稳定性原因

三、时间复杂度分析

3.1 增长曲线对比

text

n=1000时各算法大致比较次数： O(n): 1000 O(n log n): 1000 × 10 = 10000 O(n²): 1000000 n=1000000时： O(n): 1000000 O(n log n): 1000000 × 20 = 20000000 O(n²): 1000000000000（无法接受）

3.2 实际运行时间参考（n=50000随机数据）

注：数据因机器而异，但相对关系类似

四、空间复杂度分析

内存受限场景：优先选择原地排序算法。

五、场景选型指南

5.1 数据规模小（n < 1000）

5.2 数据规模中等（1000 < n < 50000）

5.3 数据规模大（n > 50000）

5.4 特殊场景

六、混合排序（工业级实现）

实际的标准库排序（C++ STLsort、JavaArrays.sort）通常采用混合策略：

1. 数据量大：用快速排序

2. 递归深度过大：切换为堆排序（防止最坏情况）

3. 分区后子数组小：用插入排序（小数组效率高）

c

// 混合排序伪代码 void hybridSort(int arr[], int left, int right) { if (right - left < THRESHOLD) { insertionSort(arr, left, right); return; } if (depth > MAX_DEPTH) { heapSort(arr, left, right); return; } int pivot = partition(arr, left, right); hybridSort(arr, left, pivot - 1, depth + 1); hybridSort(arr, pivot + 1, right, depth + 1); }

七、面试高频考点

7.1 手写代码常考

7.2 概念常考

• 稳定性的含义及判断

• 各算法的时间/空间复杂度

• 为什么快速排序实际最快（缓存友好、常数因子小）

• 堆排序为什么不稳定

• 计数排序的局限性

八、快速对比卡片

O(n²) 级（适合小数据）

O(n log n) 级（工业标准）

O(n) 级（特殊场景）

九、小结

选型口诀：

• 小数据用插入

• 要稳定用归并

• 内存紧用堆排

• 通用场景快排

• 整数范围小计数

十、思考题

1. 为什么快速排序的实际表现通常优于归并排序，即使它们的时间复杂度都是 O(n log n)？

2. 堆排序是原地排序，为什么实际应用中不如快速排序常用？

3. 计数排序和基数排序的时间复杂度都是 O(n)，它们有什么局限性？

4. 如果你需要排序一个包含100万个整数的文件，内存只有50MB，应该选择什么算法？

欢迎在评论区讨论你的答案。