十大排序算法性能深度对比

Published:
• 19 min read

排序是计算机科学中最基础、最重要的算法问题之一。无论是数据库索引的构建、搜索引擎结果的呈现，还是操作系统进程的调度，排序算法都扮演着不可或缺的角色。Donald Knuth 在其经典著作《计算机程序设计艺术》中曾指出，计算机约有 25% 的运行时间花费在排序上。深入理解各种排序算法的原理、性能特征和适用场景，是每一位程序员的必修课。

本文将对十种经典排序算法进行全面而深入的对比分析，涵盖原理讲解、复杂度分析、代码实现以及实际应用场景。

一、冒泡排序（Bubble Sort）

原理简述： 冒泡排序反复遍历待排序序列，每次比较相邻的两个元素，若顺序错误则交换。每一轮遍历会将当前未排序部分的最大元素”冒泡”到正确位置。

复杂度分析：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 若本轮无交换，说明已有序
            break
    return arr

二、选择排序（Selection Sort）

原理简述： 选择排序每次从未排序部分中找到最小（或最大）元素，将其放到已排序部分的末尾。算法维护两个子序列：已排序部分和未排序部分。

复杂度分析：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

三、插入排序（Insertion Sort）

原理简述： 插入排序将数组分为已排序和未排序两部分，每次取未排序部分的第一个元素，在已排序部分中找到合适的位置插入。类似于我们打牌时整理手牌的过程。

复杂度分析：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

插入排序在小规模数据和近乎有序的数据上表现极为优秀，许多高级排序算法（如 Timsort）在处理小规模子数组时会回退到插入排序。

四、希尔排序（Shell Sort）

原理简述： 希尔排序是插入排序的改进版本，核心思想是通过设定一个递减的间隔序列（gap sequence），先对间隔较大的元素进行排序，逐步缩小间隔，最终在间隔为 1 时退化为标准插入排序。由于前期的大间隔排序已使数据趋于有序，最终的插入排序效率大大提高。

复杂度分析：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

五、快速排序（Quick Sort）

原理简述： 快速排序采用分治策略，选取一个基准元素（pivot），将数组划分为两部分——小于基准的元素和大于基准的元素，然后对两部分递归排序。快速排序的核心在于分区操作（partition）。

复杂度分析：

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

快速排序是实践中最常用的排序算法之一，其平均性能极为优秀。通过随机化选取 pivot 或三数取中法（median-of-three），可以有效避免最坏情况。

六、归并排序（Merge Sort）

原理简述： 归并排序同样采用分治策略，将数组递归地分成两半，分别排序后再合并（merge）。合并操作是归并排序的核心，它将两个有序子数组合并为一个有序数组。

复杂度分析：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= 保证稳定性
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

归并排序性能稳定，不受输入数据分布影响，是外部排序（数据量超出内存时）的首选算法。

七、堆排序（Heap Sort）

原理简述： 堆排序利用二叉堆（通常是最大堆）这种数据结构。首先将数组构建为最大堆，然后反复将堆顶（最大值）与末尾元素交换，缩小堆的范围并重新调整堆结构，从而实现排序。

复杂度分析：

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 逐个提取堆顶元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

堆排序的优势在于最坏情况下仍保证 O(n log n) 且只需 O(1) 额外空间，但由于缓存不友好（跳跃式内存访问），实际运行速度通常不如快速排序。

八、计数排序（Counting Sort）

原理简述： 计数排序是一种非比较排序算法。它通过统计每个元素出现的次数，然后根据统计信息将元素放到正确位置。适用于数据范围有限的整数排序。

复杂度分析：

def counting_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1

    count = [0] * range_val
    output = [0] * len(arr)

    for num in arr:
        count[num - min_val] += 1

    # 累加计数
    for i in range(1, range_val):
        count[i] += count[i - 1]

    # 从后向前遍历以保持稳定性
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1

    return output

九、桶排序（Bucket Sort）

原理简述： 桶排序将数据分配到若干个”桶”中，每个桶内部独立排序（通常使用插入排序或其他排序算法），最后将所有桶的结果拼接起来。当数据均匀分布时，桶排序效率极高。

复杂度分析：

def bucket_sort(arr, bucket_count=10):
    if not arr:
        return arr
    min_val, max_val = min(arr), max(arr)
    bucket_range = (max_val - min_val) / bucket_count + 1

    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        idx = int((num - min_val) / bucket_range)
        buckets[idx].append(num)

    result = []
    for bucket in buckets:
        result.extend(insertion_sort(bucket))  # 桶内使用插入排序
    return result

十、基数排序（Radix Sort）

原理简述： 基数排序按照位数从低位到高位（LSD）或从高位到低位（MSD）依次进行排序，每一位的排序使用稳定的排序算法（通常是计数排序）。适用于整数或等长字符串排序。

复杂度分析：

def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        idx = (num // exp) % 10
        count[idx] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        idx = (arr[i] // exp) % 10
        output[count[idx] - 1] = arr[i]
        count[idx] -= 1

    for i in range(n):
        arr[i] = output[i]

完整对比表格

排序算法最好时间平均时间最坏时间空间复杂度稳定性
冒泡排序O(n)O(n²)O(n²)O(1)稳定
选择排序O(n²)O(n²)O(n²)O(1)不稳定
插入排序O(n)O(n²)O(n²)O(1)稳定
希尔排序O(n log n)O(n^1.3)O(n²)O(1)不稳定
快速排序O(n log n)O(n log n)O(n²)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)不稳定
计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定
桶排序O(n+k)O(n+k)O(n²)O(n+k)稳定
基数排序O(d(n+k))O(d(n+k))O(d(n+k))O(n+k)稳定

注：k 为数据范围或桶数量，d 为最大位数。

实际应用场景分析

小规模数据（n < 50）： 插入排序是最佳选择。常数因子小，且对近乎有序的数据极为高效。

中等规模通用排序： 快速排序在大多数场景中是最快的比较排序算法，平均情况下的常数因子很小。

需要稳定排序： 归并排序是稳定且性能可预测的 O(n log n) 算法。在需要保持相等元素原始顺序的场景中（如多关键字排序），稳定性至关重要。

内存受限： 堆排序只需 O(1) 额外空间，适合内存紧张的嵌入式系统。

数据范围有限的整数排序： 计数排序或基数排序可以实现线性时间复杂度，远超比较排序的 O(n log n) 理论下界。

大规模外部排序： 归并排序天然适合外部排序，因为其顺序访问模式适合磁盘 I/O。

数据均匀分布的浮点数排序： 桶排序可以实现接近线性的排序效率。

各语言标准库排序的底层实现

Python — Timsort

Python 的内置 sort() 和 sorted() 使用 Timsort 算法，由 Tim Peters 于 2002 年设计。Timsort 是一种混合排序算法，结合了归并排序和插入排序的优点：

Timsort 的时间复杂度为 O(n log n)，在已部分有序的数据上表现尤为出色，最好情况可达 O(n)。

C — qsort

C 标准库的 qsort() 通常基于快速排序实现，但具体实现因编译器而异。glibc 的实现采用了归并排序（当有足够内存时）或快速排序（内存不足时），并在小数组上使用插入排序优化。MSVC 的实现使用内省排序（Introsort），结合快速排序、堆排序和插入排序。

Java — Dual-Pivot Quicksort 与 Timsort

Java 对基本类型数组使用 Dual-Pivot Quicksort（双基准快速排序，由 Vladimir Yaroslavskiy 设计），选取两个基准将数组分为三部分，在实践中比经典快速排序更快。对于对象数组，Java 使用 Timsort，以保证排序的稳定性。

C++ — Introsort

C++ STL 的 std::sort 通常使用 Introsort（内省排序），由 David Musser 于 1997 年提出。它以快速排序开始，当递归深度超过 2×log₂(n) 时切换到堆排序以保证 O(n log n) 的最坏情况，对于小数组则使用插入排序。

Go — Pattern-Defeating Quicksort (pdqsort)

Go 语言标准库采用 pdqsort，这是一种现代化的混合排序算法，在随机数据上接近快速排序的性能，同时能高效处理已排序、逆序、大量重复等特殊模式的数据。

总结与选择建议

排序算法没有绝对的”最好”，只有最适合特定场景的选择。以下是简要的决策指南：

  1. 不确定时，使用语言标准库：现代语言标准库的排序实现经过精心优化，是大多数场景的最佳选择。
  2. 追求通用性能：快速排序及其变体（Introsort、pdqsort）是最佳选择。
  3. 需要稳定排序：选择归并排序或 Timsort。
  4. 内存极度受限：选择堆排序（O(1) 空间、O(n log n) 时间）。
  5. 数据特征明确：
    • 数据范围小 → 计数排序
    • 整数且位数有限 → 基数排序
    • 均匀分布 → 桶排序
    • 近乎有序 → 插入排序或 Timsort
  6. 教学与面试：冒泡排序和选择排序适合理解排序的基本概念，但在生产环境中几乎不使用。

理解这些算法不仅有助于选择合适的排序方案，更能培养分析问题、设计算法的思维能力。比较排序的理论下界是 O(n log n)，而非比较排序在特定条件下可以突破这一限制——这一思想本身就是算法设计中”打破常规约束”的精妙范例。

分享到：
分享到QQ 分享到 X 分享到 Telegram 分享到 Facebook