806 内部排序算法的比较和应用

内部排序算法的比较和应用

算法的比较

• 冒泡排序 (Bubble Sort)
  • 时间复杂度:
    • 平均: $O(n^2)$
    • 最坏: $O(n^2)$ (序列逆序)
    • 最好: $O(n)$ (序列已排序，并使用标志位优化)
  • 空间复杂度: $O(1)$
  • 稳定性: 稳定
  • 一趟后确定最终位置: 是 (每趟将一个最值元素放到最终位置)
  • 排序趟数是否与初始序列有关：是 - 排序趟数受初始序列影响，最好情况下可提前结束
  • 比较与交换次数:
    • 比较次数: 最好情况为 $O(n)$，最坏和平均情况为 $O(n^2)$。
    • 交换次数: 最好情况为 $0$，最坏和平均情况为 $O(n^2)$。
  • 过程特征: 相邻元素比较与交换。
  • 适用存储结构: 顺序存储（数组）效果好；链式存储可实现，但效率较低。
• 选择排序 (Selection Sort)
  • 时间复杂度:
    • 平均: $O(n^2)$
    • 最坏: $O(n^2)$
    • 最好: $O(n^2)$ (比较次数与数据初始状态无关)
  • 空间复杂度: $O(1)$
  • 稳定性: 不稳定 (远距离交换可能破坏相等元素的相对顺序，例如 5 8 5 2 9)
  • 一趟后确定最终位置: 是 (每趟从待排区选出最值元素放到最终位置)
  • 排序趟数是否与初始序列有关：否 - 始终需要 n-1 趟，与初始序列无关
  • 比较与交换次数:
    • 比较次数: 始终为 $O(n^2)$，与初始序列无关。
    • 交换次数: 始终为 $O(n)$。核心优点是交换次数少。
  • 过程特征: 每次选择全局最值。
  • 适用存储结构: 顺序存储（数组）。不适合链表，因为查找最值需要遍历，效率低。
• 插入排序 (Insertion Sort)
  • 时间复杂度:
    • 平均: $O(n^2)$
    • 最坏: $O(n^2)$ (序列逆序)
    • 最好: $O(n)$ (序列已排序)
  • 空间复杂度: $O(1)$
  • 稳定性: 稳定
  • 一趟后确定最终位置: 否 (后续插入可能移动已“有序”的元素)
  • 排序趟数是否与初始序列有关：是 - 排序趟数和比较次数受初始序列影响
  • 比较与交换次数:
    • 比较次数: 最好情况为 $O(n)$，最坏和平均情况为 $O(n^2)$。
    • 元素移动次数: 最好情况为 $0$，最坏和平均情况为 $O(n^2)$。
  • 过程特征: 将元素插入到已排序的子序列中。对基本有序的数据非常高效。
  • 适用存储结构: 顺序存储和链式存储均可。在链表上表现优异，可避免元素后移，仅需修改指针。
• 希尔排序 (Shell Sort)
  • 时间复杂度:
    • 平均: $O(n^{1.3})$ 到 $O(n^{1.5})$ (依赖增量序列)
    • 最坏: $O(n^2)$ (例如 Hibbard 增量序列)
    • 最好: $O(n{\log }^{2}n)$ (Sedgewick 增量序列)
  • 空间复杂度: $O(1)$
  • 稳定性: 不稳定 (分组插入，不同组的相等元素在后续趟中可能改变相对顺序)
  • 一趟后确定最终位置: 否 (任何一趟都只是宏观调整，使序列趋于有序)
  • 排序趟数是否与初始序列有关：是 - 不同初始序列可能导致不同的比较和交换次数
  • 比较与交换次数: 数量级与时间复杂度相同，具体次数依赖于增量序列。
  • 过程特征: 分组的插入排序，也称缩小增量排序。通过逐步缩小的增量进行排序。
  • 适用存储结构: 顺序存储（数组）。不适合链表，因其依赖随机访问进行分组。
• 快速排序 (Quick Sort)
  • 时间复杂度:
    • 平均: $O(n\log n)$
    • 最坏: $O(n^2)$ (序列有序或逆序，导致划分极不均衡)
    • 最好: $O(n\log n)$ (每次划分都均分)
  • 空间复杂度: 平均 $O(\log n)$，最坏 $O(n)$ (递归栈深度)
  • 稳定性: 不稳定 (基准元的交换可能打乱相等元素的顺序)
  • 一趟后确定最终位置: 是 (Partition 操作后，基准元（Pivot）的位置即为最终位置)
  • 排序趟数是否与初始序列有关：是 - 初始序列影响分区效果和递归深度
  • 比较与交换次数:
    • 比较次数: 平均 $O(n\log n)$，最坏 $O(n^2)$。
    • 交换次数: 平均 $O(n\log n)$，最坏 $O(n^2)$。
  • 过程特征: 分治思想，通过基准元划分序列。是平均性能最好的内部排序算法。
  • 适用存储结构: 顺序存储（数组）。不适合链表，因其依赖随机访问进行划分。
• 归并排序 (Merge Sort)
  • 时间复杂度:
    • 平均: $O(n\log n)$
    • 最坏: $O(n\log n)$
    • 最好: $O(n\log n)$
  • 空间复杂度: $O(n)$ (用于合并的辅助数组)
  • 稳定性: 稳定 (合并时保证相等元素的相对顺序即可)
  • 一趟后确定最终位置: 否 (只有最后一次合并完成后才能确定所有元素位置)
  • 排序趟数是否与初始序列有关：否 - 排序趟数固定，只与数据规模有关
  • 比较与交换次数:
    • 比较次数: 始终为 $O(n\log n)$。
    • 元素移动次数: 始终为 $O(n\log n)$。
  • 过程特征: 分治思想，先分解再合并。性能稳定，是外部排序的基础。
  • 适用存储结构: 顺序存储和链式存储均可。在链表上实现可将空间复杂度降至 $O(1)$ (指辅助空间，递归栈仍需 $O(\log n)$)。
• 堆排序 (Heap Sort)
  • 时间复杂度:
    • 平均: $O(n\log n)$
    • 最坏: $O(n\log n)$
    • 最好: $O(n\log n)$
  • 空间复杂度: $O(1)$ (原地排序)
  • 稳定性: 不稳定 (堆顶与堆底交换可能破坏相等元素的顺序)
  • 一趟后确定最终位置: 是 (建堆后，每次调整将堆顶（最值）放到序列末尾的最终位置)
  • 排序趟数是否与初始序列有关：否 - 建堆和调整的过程与初始序列无关
  • 比较与交换次数:
    • 比较次数: $O(n\log n)$。
    • 交换次数: $O(n\log n)$。
  • 过程特征: 构建堆（大顶堆或小顶堆），然后将堆顶元素与末尾元素交换并调整堆。
  • 适用存储结构: 顺序存储（数组）。不适合链表，因建堆和调整堆依赖于父子节点的下标计算。
• 计数排序 (Counting Sort)
  • 时间复杂度: $O(n+k)$ (k 为待排数据范围，即 max-min+1)
  • 空间复杂度: $O(k)$ (计数数组)
  • 稳定性: 稳定 (通过从后往前遍历原始数组来填充结果数组可保证)
  • 一趟后确定最终位置: 是 (非比较排序，无“趟”概念，位置通过频次和累加一次性确定)
  • 排序趟数是否与初始序列有关：否 - 排序过程与初始序列的排列无关
  • 比较与交换次数: 无。属于非比较排序，不涉及元素间的比较。
  • 过程特征: 非比较排序，通过统计频次确定位置。适用于整数且数据范围不大的场景。
  • 适用存储结构: 顺序存储（数组）。
• 桶排序 (Bucket Sort)
  • 时间复杂度:
    • 平均: $O(n+k)$ (k 为桶数量)
    • 最坏: $O(n^2)$ (所有元素落入同一桶，且桶内使用 $O(n^2)$ 算法)
  • 空间复杂度: $O(n+k)$
  • 稳定性: 稳定 (取决于桶内排序算法是否稳定以及元素入桶方式)
  • 一趟后确定最终位置: 否 (分桶操作不能确定最终位置)
  • 排序趟数是否与初始序列有关：是 - 元素分布影响桶的数量和每个桶内的排序
  • 比较与交换次数: 无 (顶层逻辑)。比较和交换发生在桶内排序阶段。
  • 过程特征: 非比较排序，将元素分配到桶中再对各桶分别排序。适用于数据均匀分布的场景。
  • 适用存储结构: 顺序存储（数组）和链式存储（桶的实现）结合。
• 基数排序 (Radix Sort)
  • 时间复杂度: $O(d(n+r))$ (d 为关键字位数, r 为基数，即桶的数量)
  • 空间复杂度: $O(n+r)$
  • 稳定性: 稳定 (其正确性依赖于内部使用的分配和收集算法是稳定的)
  • 一趟后确定最终位置: 否 (低位排序不能确定最终位置，只有最高位排完才最终确定)
  • 排序趟数是否与初始序列有关：否 - 排序趟数只与最大值的位数有关
  • 比较与交换次数: 无。属于非比较排序，不涉及元素间的比较。
  • 过程特征: 非比较排序，按关键字的各位进行分配和收集。适用于位数固定或不长的非负整数。
  • 适用存储结构: 顺序存储（数组）和链式存储（实现队列分配）。

算法的应用

选取排序算法需要考虑的因素

在实际应用中选择合适的排序算法，需要综合考虑以下因素：

1. 待排序元素的数量 $n$：
   • 小规模数据：对于 $n$ 较小（如 $n<50$）的数据，简单排序算法（如插入排序、冒泡排序、选择排序）可能更合适，因为它们的常数因子较小，且实现简单。
   • 大规模数据：对于 $n$ 较大（如 $n>1000$）的数据，时间复杂度为 $O(n\log n)$ 的算法（如快速排序、归并排序、堆排序）通常是首选。
2. 待排序元素的特性：
   • 是否基本有序：如果数据基本有序，插入排序、冒泡排序、希尔排序在最好情况下能达到 $O(n)$ 或接近 $O(n)$ 的时间复杂度，性能较好。
   • 数据范围和分布：
     • 如果待排序元素是整数，且范围 $k$ 不大，计数排序、桶排序、基数排序（非比较排序）可能比比较排序算法更快，达到 $O(n+k)$ 或 $O(d(n+r))$。
     • 如果数据均匀分布，桶排序效果会很好。
     • 如果数据有许多重复值，计数排序或桶排序可能更高效。
3. 对稳定性的要求：
   • 如果排序后，相等元素的相对顺序必须保持不变，则必须选择稳定排序算法，如冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序。
   • 如果稳定性不是必要条件，则可以选择不稳定但可能更快（如平均情况下的快速排序）的算法。
4. 对空间复杂度的要求：
   • 内存限制：如果系统内存资源有限，应选择空间复杂度为 $O(1)$ 的原地排序算法（如冒泡排序、选择排序、插入排序、堆排序）。
   • 外部排序：对于数据量超出内存容量的情况，需要使用外部排序算法，其中归并排序是常用的方法。
5. 编程实现的难易程度：
   • 简单排序算法（冒泡、选择、插入）实现起来相对容易。
   • 快速排序、归并排序、堆排序等实现相对复杂，但通常有库函数可用。
6. 数据类型：
   • 比较排序算法适用于各种可比较的数据类型。
   • 非比较排序算法（计数、桶、基数）通常仅适用于整数或可映射为整数的数据。

小结

• 快速排序：通常被认为是综合性能最好的排序算法之一，平均时间复杂度为 $O(n\log n)$，但最坏情况为 $O(n^2)$，且不稳定。适用于大规模数据的排序。
• 归并排序：时间复杂度稳定在 $O(n\log n)$，且稳定，空间复杂度为 $O(n)$。在需要稳定排序或进行外部排序时是很好的选择。
• 堆排序：时间复杂度稳定在 $O(n\log n)$，原地排序（空间复杂度 $O(1)$），但不稳定。适用于对空间有严格要求的大规模数据排序。
• 插入排序/冒泡排序/选择排序：简单易实现，适用于小规模数据或部分有序数据。
• 计数排序/桶排序/基数排序：非比较排序，时间复杂度可以达到 $O(n)$ 级别，但对数据类型和范围有特定要求。适用于整数排序，且数据范围不大或分布均匀的情况。

在实际开发中，通常会使用标准库提供的排序函数（如 C++ 的 std::sort），这些库函数通常会结合多种排序算法的优点，例如，std::sort 通常是内省排序（IntroSort），它结合了快速排序、堆排序和插入排序。