如何选择排序算法

数据规模：

  • 小规模数据（<1000）：插入排序、选择排序
  • 中等规模：快速排序、归并排序、堆排序
  • 大规模数据：快速排序、归并排序、基数排序

数据类型：

  • 整数：计数排序、基数排序
  • 浮点数：快速排序、归并排序
  • 字符串：基数排序、快速排序

内存限制：

  • 内存充足：归并排序
  • 内存受限：堆排序、原地快速排序

稳定性要求：

  • 需要稳定：归并排序、插入排序
  • 不需要稳定：快速排序、堆排序

数据分布：

  • 近乎有序：插入排序
  • 完全随机：快速排序
  • 大量重复元素：三路快排

是否并行：

  • 需要并行：归并排序
  • 不需要并行：快速排序

不同排序算法的比较和应用场景

快速排序：

场景：通用场景，特别是随机分布的大规模数据

优点：平均情况下最快

缺点：最坏情况性能差，不稳定

归并排序：

场景：需要稳定排序，外部排序

优点：稳定，性能稳定

缺点：需要额外空间

堆排序：

场景：大数据集，需要找出最大/最小的k个元素

优点：空间效率高，最坏情况也是O(n log n)

缺点：不稳定，实际运行时间often比快排慢

插入排序：

场景：小数据集，几乎已排序的数据

优点：简单，对小数据集很高效

缺点：大数据集效率低

计数排序：

场景：数据范围已知且较小的整数排序

优点：线性时间复杂度

缺点：只适用于整数，需要额外空间

基数排序：

场景：整数或字符串排序，尤其是长度相近时

优点：可以达到线性时间复杂度

缺点：需要额外空间，只适用于可以分割成位的数据

如何优化特定的排序算法

快速排序优化：

  • 三数取中法选择pivot
  • 对小规模子数组使用插入排序
  • 三路快排处理重复元素

归并排序优化：

  • 小规模子数组使用插入排序
  • 避免在合并时重复复制已经有序的元素

堆排序优化：

  • 使用Floyd建堆算法
  • 优化下沉操作，减少比较次数

插入排序优化：

  • 使用二分查找找到插入位置
  • 移动元素时使用赋值而不是交换
排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 特点
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定 实现最简单
插入排序 O(n²) O(n²) O(n) O(1) 稳定 小数据集效率高
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定 分治法，稳定排序
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定 适用于已知范围的整数
基数排序 O(N*M) O(N*M) O(N*M) O(M) 稳定 适用于整数和字符串
选择排序 O(n²) O(n²) O(n) O(1) 不稳定 实现简单
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定 分治法，通常最快
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 原地排序，适合大数据