数据结构补充教程——排序算法与复杂度分析

概述

排序算法是计算机科学中最基础、最经典的算法问题之一。本教程系统梳理各种排序算法的原理、实现与性能特征，深入分析时间复杂度与空间复杂度的计算方法，并介绍常见的算法优化策略。理解排序算法不仅有助于解决实际编程问题，更是掌握算法设计与分析方法论的重要入口。

知识点一：基本排序算法

1. 冒泡排序（Bubble Sort）

核心思想：相邻元素两两比较，将较大的元素逐步"冒泡"到数组末尾。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 优化：无交换则已有序
            break
    return arr

• 时间复杂度：最优 \(O(n)\)（已有序），最坏/平均 \(O(n^2)\)
• 空间复杂度：\(O(1)\)
• 稳定性：稳定

2. 选择排序（Selection Sort）

核心思想：每次从未排序部分选择最小元素，放到已排序部分的末尾。

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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

• 时间复杂度：无论输入如何，始终为 \(O(n^2)\)（比较次数固定）
• 空间复杂度：\(O(1)\)
• 稳定性：不稳定

3. 插入排序（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

• 时间复杂度：最优 \(O(n)\)（已有序），最坏 \(O(n^2)\)，平均 \(O(n^2)\)
• 空间复杂度：\(O(1)\)
• 稳定性：稳定
• 特点：对近乎有序的数据效率极高，常作为高级排序的"收尾"手段

知识点二：高级排序算法

1. 快速排序（Quick Sort）

核心思想：选择一个基准元素（pivot），将数组分为"小于基准"和"大于基准"两部分，递归排序。

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)

原地分区版本（更高效）：

def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx - 1)
        quick_sort_inplace(arr, pivot_idx + 1, high)

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

• 时间复杂度：最优/平均 \(O(n \log n)\)，最坏 \(O(n^2)\)（每次选到极端值）
• 空间复杂度：\(O(\log n)\)（递归栈深度）
• 稳定性：不稳定

优化策略：

• 三数取中法：选取首、中、尾三个元素的中位数作为基准
• 随机化：随机选择基准元素，避免最坏情况
• 小数组切换：当子数组长度小于阈值（如 10）时切换为插入排序

2. 归并排序（Merge Sort）

核心思想：将数组递归地分成两半，分别排序后合并。典型的"分治法"应用。

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

• 时间复杂度：始终 \(O(n \log n)\)，不受输入数据影响
• 空间复杂度：\(O(n)\)（需要额外空间合并）
• 稳定性：稳定
• 特点：性能稳定，适合链表排序和外部排序

3. 堆排序（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, right = 2 * i + 1, 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)\)
• 稳定性：不稳定

知识点三：时间复杂度与空间复杂度分析

时间复杂度

时间复杂度描述算法运行时间随输入规模增长的增长趋势，使用大 \(O\) 记号。

常见复杂度排序：

\(O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\)

分析方法：

1. 基本操作计数法：统计最内层循环的执行次数
2. 递推关系法：对递归算法建立递推式，如归并排序的 \(T(n) = 2T(n/2) + O(n)\)
3. 主定理（Master Theorem）：求解形如 \(T(n) = aT(n/b) + f(n)\) 的递推式

主定理简述：设 \(T(n) = aT(n/b) + O(n^d)\)

• 若 \(d > \log_b a\)，则 \(T(n) = O(n^d)\)
• 若 \(d = \log_b a\)，则 \(T(n) = O(n^d \log n)\)
• 若 \(d < \log_b a\)，则 \(T(n) = O(n^{\log_b a})\)

例题：用主定理分析归并排序 \(T(n) = 2T(n/2) + O(n)\)。

\(a = 2, b = 2, d = 1\)，\(\log_b a = \log_2 2 = 1 = d\)，属于第二种情况。

\(T(n) = O(n \log n)\) ✓

空间复杂度

空间复杂度描述算法所需额外空间随输入规模增长的趋势。

关键分析要点：

• 原地排序（如冒泡、插入、选择、堆排序）空间复杂度为 \(O(1)\)
• 递归算法需考虑递归栈深度：快速排序最优 \(O(\log n)\)，最坏 \(O(n)\)
• 归并排序需要 \(O(n)\) 额外空间存储合并结果

排序算法综合比较

知识点四：排序算法的优化策略

1. 混合排序（Introsort）

结合快速排序、堆排序和插入排序的优点：

• 一般情况使用快速排序（平均性能最优）
• 递归深度过深时切换为堆排序（避免最坏情况）
• 小数组使用插入排序（常数因子小）

C++ STL 的 std::sort 就是基于 Introsort 实现的。

2. Tim Sort

Python 内置的排序算法，结合归并排序和插入排序：

• 将数组分成若干"run"（天然有序的子序列）
• 对每个 run 使用插入排序
• 使用改进的归并策略合并 run

特点：对现实世界中部分有序的数据表现极优，最优 \(O(n)\)，最坏 \(O(n \log n)\)。

3. 计数排序、桶排序、基数排序

这三种排序不基于比较，可以突破 \(O(n \log n)\) 的下界：

• 计数排序：\(O(n+k)\)，\(k\) 为数据范围，适合范围不大的整数排序
• 桶排序：\(O(n)\)（平均），将数据分配到若干桶中分别排序
• 基数排序：\(O(d \cdot n)\)，按位排序，\(d\) 为最大位数

知识点五：排序算法的选择指南

选择原则

1. 数据规模小（\(n < 50\)）：插入排序，常数因子小，实现简单
2. 数据近乎有序：插入排序，最优 \(O(n)\)
3. 一般情况追求平均性能：快速排序，\(O(n \log n)\) 且缓存友好
4. 需要稳定排序：归并排序或 Tim Sort
5. 内存受限：堆排序，\(O(1)\) 额外空间
6. 整数且范围不大：计数排序或基数排序

例题

问题：对一个包含 100 万个整数的数组排序，整数范围在 0 到 1000 之间，应选择什么排序算法？

分析：

• 数据范围小（0~1000），整数类型
• 计数排序最合适：\(O(n+k) = O(10^6 + 1001) \approx O(n)\)
• 比较排序（如快排）的 \(O(n \log n) \approx O(20 \times 10^6)\) 慢得多

结论：选择计数排序。

练习题

题目一

对序列 [5, 2, 4, 6, 1, 3] 进行快速排序，选择最后一个元素为基准，请写出第一轮分区后的结果。

解答：

基准 pivot = 3。

遍历过程：

• 2 < 3 → 移到左侧
• 1 < 3 → 移到左侧
• 5, 4, 6 > 3 → 保持在右侧

第一轮分区后：[2, 1, 3, 6, 4, 5]，基准 3 在位置 2（索引从 0 开始）。

题目二

用主定理分析以下递推式的时间复杂度：\(T(n) = 4T(n/2) + O(n^2)\)

解答：

\(a = 4, b = 2, d = 2\)

\(\log_b a = \log_2 4 = 2 = d\)

属于主定理第二种情况：\(T(n) = O(n^2 \log n)\)

题目三

为什么选择排序是不稳定的？请举出反例。

解答：

考虑序列 [(5,a), (5,b), (2,c)]，括号中第一个值为排序键，第二个为标识。

第一轮选择最小值 2，与第一个元素交换：[(2,c), (5,b), (5,a)]

可以看到，原来在前面的 (5,a) 跑到了 (5,b) 后面，相同键值的相对顺序发生了改变，因此选择排序不稳定。

题目四

一个几乎有序的数组（每个元素距其最终位置不超过 \(k\)），用什么排序算法最合适？时间复杂度是多少？

解答：

使用插入排序或将数组分成大小为 \(k\) 的组分别排序后归并。

更优的方案是使用大小为 \(k+1\) 的最小堆：

1. 将前 \(k+1\) 个元素建堆 → \(O(k)\)
2. 每次取出堆顶（最小值），放入下一个元素 → \(O(n \log k)\)

总时间复杂度：\(O(n \log k)\)。当 \(k\) 远小于 \(n\) 时，接近 \(O(n)\)。

题目五

为什么说基于比较的排序算法时间复杂度下界是 \(O(n \log n)\)？

解答：

\(n\) 个不同元素有 \(n!\) 种排列，每次比较最多将可能的排列数减半。

决策树的高度 \(h\) 满足：\(2^h \ge n!\)

\(h \ge \log_2(n!) \approx \log_2\left(\sqrt{2\pi n} \left(\frac{n}{e}\right)^n\right) = O(n \log n)\)

因此任何基于比较的排序算法，在最坏情况下至少需要 \(O(n \log n)\) 次比较。

总结

本教程系统梳理了排序算法的核心知识：

1. 基本排序：冒泡、选择、插入排序，时间复杂度 \(O(n^2)\)，适合小规模数据和教学理解。
2. 高级排序：快速排序（平均最优）、归并排序（稳定且性能一致）、堆排序（原地且最坏有保障），时间复杂度均为 \(O(n \log n)\)。
3. 复杂度分析：掌握大 \(O\) 记号、主定理等分析工具，能够对算法性能做出准确判断。
4. 优化策略：混合排序、Tim Sort、非比较排序等，体现了算法工程中的实用智慧。
5. 选择原则：根据数据特征（规模、有序性、稳定性需求、数据类型）选择最合适的排序算法。

排序算法的学习不仅仅是记住几个代码模板，更重要的是理解其背后的设计思想（分治、贪心、空间换时间）和分析方法。这些思想贯穿整个算法与数据结构的学习，是成为优秀程序员的必经之路。