常见排序算法的时间复杂度和空间复杂度

以下是常见排序算法的时间复杂度和空间复杂度的总结，列出了最佳、平均和最坏情况下的时间复杂度，以及空间复杂度。所有复杂度以大 O 表示法表示。

排序算法 最佳时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定
冒泡排序 ( O(n) ) ( O(n^2) ) ( O(n^2) ) ( O(1) ) 是
选择排序 ( O(n^2) ) ( O(n^2) ) ( O(n^2) ) ( O(1) ) 否
插入排序 ( O(n) ) ( O(n^2) ) ( O(n^2) ) ( O(1) ) 是
希尔排序 ( O(n \log n) ) 取决于步长序列（如 ( O(n^{1.3}) )） ( O(n^2) ) ( O(1) ) 否
归并排序 ( O(n \log n) ) ( O(n \log n) ) ( O(n \log n) ) ( O(n) ) 是
快速排序 ( O(n \log n) ) ( O(n \log n) ) ( O(n^2) ) ( O(\log n) )（递归栈） 否
堆排序 ( O(n \log n) ) ( O(n \log n) ) ( O(n \log n) ) ( O(1) ) 否
计数排序 ( O(n + k) ) ( O(n + k) ) ( O(n + k) ) ( O(k) ) 是
桶排序 ( O(n + k) ) ( O(n + k) ) ( O(n^2) ) ( O(n + k) ) 是
基数排序 ( O(n \cdot k) ) ( O(n \cdot k) ) ( O(n \cdot k) ) ( O(n + k) ) 是

说明

  1. 时间复杂度：

    • 最佳情况：输入数据已经接近有序（如冒泡排序、插入排序）或特定条件（如快速排序选择好的枢轴）。
    • 平均情况：基于随机输入数据的期望复杂度。
    • 最坏情况：输入数据完全逆序或最不利情况（如快速排序的枢轴选择不佳）。
    • ( n ) 表示输入元素数量，( k ) 表示计数排序或基数排序中的范围或位数。

  2. 空间复杂度：

    • ( O(1) )：原地排序算法（如冒泡、选择、插入、堆排序）。
    • ( O(n) )：需要额外数组（如归并排序）。
    • ( O(\log n) )：快速排序的递归调用栈平均情况。
    • ( O(k) ) 或 ( O(n + k) )：计数排序、桶排序、基数排序依赖于辅助数据结构。

  3. 稳定性：

    • 稳定排序：相同值的元素在排序后保持相对顺序（如冒泡、插入、归并、计数、桶、基数排序）。
    • 非稳定排序：可能改变相同值元素的相对顺序（如选择、希尔、快速、堆排序）。

  4. 特殊说明：

    • 希尔排序：时间复杂度取决于步长序列（如增量为 ( 2^k ) 或 Sedgewick 序列）。
    • 快速排序：最坏情况 ( O(n^2) ) 通常可通过随机化枢轴或三路划分优化到接近 ( O(n \log n) )。
    • 计数排序、桶排序、基数排序：适用于特定数据范围（如整数或有限范围值），( k ) 表示范围或位数。

如果需要某算法的详细代码示例或进一步分析，请告诉我！