排序算法复杂度比较

排序算法复杂度比较

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

基本概念

时间复杂度

时间复杂度描述算法执行时间随输入规模增长的变化趋势，通常用大O符号（$O(n)$）表示。排序算法的时间复杂度分为：

• 最好情况：输入数据已满足排序要求时的性能。
• 最坏情况：输入数据完全逆序时的性能。
• 平均情况：随机输入数据时的期望性能。

空间复杂度

空间复杂度描述算法运行过程中所需的额外存储空间。排序算法可分为：

• 原地排序：空间复杂度为$O(1)$，仅需常数级额外空间（如冒泡排序）。
• 非原地排序：需要额外存储空间（如归并排序）。

稳定性

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

常见排序算法复杂度比较

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

排序算法复杂度比较

算法名称	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$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\log n)$	$O(n^2)$	$O(\log n)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定

算法选择建议

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

代码示例

快速排序（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))

输出：

输入: [3, 6, 8, 10, 1, 2, 1]
输出: [1, 1, 2, 3, 6, 8, 10]

归并排序（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));
    }
}

实际应用场景

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

复杂度对比图

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

数学推导（选读）

快速排序的平均时间复杂度推导： $T(n)=2T(n/2)+O(n)⟹T(n)=O(n\log n)$