075-排序算法

常见的排序算法可分为比较排序和非比较排序两大类，以下是主要分类及典型算法：

基础排序
- 冒泡排序（Bubble Sort）
  - 时间复杂度：O(n²)
  - 特点：相邻元素交换，稳定排序
  - 优化：加入 flag 判断提前终止
- 选择排序（Selection Sort）
  - 时间复杂度：O(n²)
  - 特点：每次选择最小元素放到前面，不稳定（交换可能破坏顺序）
- 插入排序（Insertion Sort）
  - 时间复杂度：O(n²)（最好情况 O(n)）
  - 特点：适合小规模或基本有序数据，稳定
分治排序
- 快速排序（Quick Sort）
  - 平均时间复杂度：O(nlogn)
  - 最坏情况：O(n²)（已排序数据+基准选择不当）
  - 特点：原地排序，不稳定，实际应用最广泛
- 归并排序（Merge Sort）
  - 时间复杂度：O(nlogn)
  - 特点：稳定排序，需要额外 O(n) 空间，适合外部排序
高效改进型
- 希尔排序（Shell Sort）
  - 时间复杂度：O(n^(1.3~2))
  - 特点：插入排序的改进，通过分组增量提升效率
- 堆排序（Heap Sort）
  - 时间复杂度：O(nlogn)
  - 特点：利用堆结构，不稳定，空间复杂度 O(1)

计数排序（Counting Sort）
- 时间复杂度：O(n + k)（k 为数据范围）
- 适用场景：整数且数据范围较小（如年龄排序）
桶排序（Bucket Sort）
- 时间复杂度：O(n + k)（k 为桶数量）
- 特点：数据均匀分布时高效，需要额外空间
基数排序（Radix Sort）
- 时间复杂度：O(d(n + k))（d 为位数，k 为基数）
- 特点：按位排序，稳定，适合整数或定长字符串

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(n²)	O(1)	稳定	教学演示
快速排序	O(nlogn)	O(n²)	O(logn)	不稳定	通用数据
归并排序	O(nlogn)	O(nlogn)	O(n)	稳定	大数据量外部排序
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定	实时系统（无最坏情况）
计数排序	O(n + k)	O(n + k)	O(k)	稳定	小范围整数
基数排序	O(d(n + k))	O(d(n + k))	O(n + k)	稳定	多位数排序

语言内置排序
- Python：list.sort() 使用 TimSort（归并+插入）
- Java：Arrays.sort() 对基本类型用双轴快排，对象用 TimSort
- C++：std::sort() 使用 IntroSort（快速+堆排序）
选择策略
- 小数据量（n ≤ 50）：插入排序（常数项小）
- 通用场景：快速排序（注意随机化基准选择）
- 需要稳定：归并排序
- 已知数据范围：计数/桶/基数排序

数据规模 n=10000 的排序耗时示例（单位：毫秒）：
- 冒泡排序：≈1200ms
- 插入排序：≈200ms
- 快速排序：≈2ms
- 计数排序（k=1000）：≈1ms

（测试环境：Intel i7-11800H @2.3GHz）