编辑“︁排序算法复杂度比较”︁

= 排序算法复杂度比较 =

排序算法是计算机科学中最基础且重要的算法类别之一，用于将一组数据按照特定顺序（如升序或降序）重新排列。不同的排序算法在时间复杂度、空间复杂度以及稳定性等方面表现各异。本页将详细介绍常见排序算法的复杂度比较，帮助初学者和程序员选择适合场景的算法。

== 基本概念 ==
=== 时间复杂度 ===
时间复杂度描述算法执行时间随输入规模增长的变化趋势，通常用大O符号（<math>O(n)</math>）表示。排序算法的时间复杂度分为：
* '''最好情况'''：输入数据已满足排序要求时的性能。
* '''最坏情况'''：输入数据完全逆序时的性能。
* '''平均情况'''：随机输入数据时的期望性能。

=== 空间复杂度 ===
空间复杂度描述算法运行过程中所需的额外存储空间。排序算法可分为：
* '''原地排序'''：空间复杂度为<math>O(1)</math>，仅需常数级额外空间（如冒泡排序）。
* '''非原地排序'''：需要额外存储空间（如归并排序）。

=== 稳定性 ===
若排序后相等元素的相对顺序保持不变，则称算法是'''稳定的'''（如插入排序）。否则为'''不稳定的'''（如快速排序）。

== 常见排序算法复杂度比较 ==
下表总结了常见排序算法的时间复杂度、空间复杂度和稳定性：

{| class="wikitable"
|+ 排序算法复杂度比较
! 算法名称 !! 最好时间复杂度 !! 平均时间复杂度 !! 最坏时间复杂度 !! 空间复杂度 !! 稳定性
|-
| 冒泡排序 || <math>O(n)</math> || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>O(1)</math> || 稳定
|-
| 选择排序 || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>O(1)</math> || 不稳定
|-
| 插入排序 || <math>O(n)</math> || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>O(1)</math> || 稳定
|-
| 快速排序 || <math>O(n \log n)</math> || <math>O(n \log n)</math> || <math>O(n^2)</math> || <math>O(\log n)</math> || 不稳定
|-
| 归并排序 || <math>O(n \log n)</math> || <math>O(n \log n)</math> || <math>O(n \log n)</math> || <math>O(n)</math> || 稳定
|-
| 堆排序 || <math>O(n \log n)</math> || <math>O(n \log n)</math> || <math>O(n \log n)</math> || <math>O(1)</math> || 不稳定
|}

== 算法选择建议 ==
* '''小规模数据'''（如<math>n < 100</math>）：插入排序或冒泡排序（代码简单，常数因子小）。
* '''中等规模数据'''：快速排序或归并排序（平均<math>O(n \log n)</math>）。
* '''大规模数据且内存受限'''：堆排序（原地排序，最坏情况<math>O(n \log n)</math>）。
* '''需要稳定性'''：归并排序或插入排序。

== 代码示例 ==
=== 快速排序（Python） ===
<syntaxhighlight lang="python">
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 示例输入与输出
input_arr = [3, 6, 8, 10, 1, 2, 1]
print("输入:", input_arr)
print("输出:", quick_sort(input_arr))
</syntaxhighlight>
'''输出：'''
<pre>
输入: [3, 6, 8, 10, 1, 2, 1]
输出: [1, 1, 2, 3, 6, 8, 10]
</pre>

=== 归并排序（Java） ===
<syntaxhighlight lang="java">
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // 合并逻辑（略）
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("输入: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("输出: " + Arrays.toString(arr));
    }
}
</syntaxhighlight>

== 实际应用场景 ==
* '''数据库索引'''：B树排序使用类似快速排序的划分策略。
* '''大数据处理'''：MapReduce框架中，归并排序用于合并分布式计算结果。
* '''游戏开发'''：插入排序动态更新排行榜（数据近乎有序时效率高）。

== 复杂度对比图 ==
<mermaid>
barChart
    title 排序算法平均时间复杂度比较
    xAxis 算法
    yAxis 时间
    series
        "O(n²)": 冒泡排序, 选择排序, 插入排序
        "O(n log n)": 快速排序, 归并排序, 堆排序
</mermaid>

== 数学推导（选读） ==
快速排序的平均时间复杂度推导：
<math>
T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)
</math>

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:排序算法]]