给数据排排队 —— 经典排序算法

排序是计算机科学中研究最深入的问题之一。从最朴素的两两比较，到巧妙的分治策略，排序算法的演进史就是一部人类智慧的缩影。

📋 开篇自测：你已经知道多少？

Python内置的sorted()函数用的是什么排序算法？为什么选它？

快速排序平均很快，但最坏情况下和冒泡排序一样慢——什么情况下会这样？

为什么说”基于比较的排序算法，时间复杂度不可能低于O(n log n)“？

一、为什么要学排序

你可能觉得排序很简单——调用一下sort()不就行了？确实，日常编程中你很少需要自己写排序算法。但学习排序有三个重要价值：

训练算法思维： 排序算法涵盖了暴力、分治、递归、堆等核心思想
理解性能差异： 知道为什么有些排序”天生慢”，有些”天生快”
做出正确选择： 不同场景适合不同排序方法，了解它们才能选对

让我们按照从简单到复杂的顺序，逐一拆解最经典的排序算法。

二、冒泡排序——最笨但最直观的方法

思路

想象一杯可乐里的气泡，大气泡会慢慢浮到水面上。冒泡排序就是让大的元素像气泡一样一步步”冒”到数组的末尾。

每一轮遍历，比较相邻的两个元素，如果前面的比后面的大就交换。一轮下来，最大的元素就到了末尾。重复n-1轮，整个数组就排好了。

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

data = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data))  # [11, 12, 22, 25, 34, 64, 90]

时间复杂度： 平均和最坏都是O(n²)，最好（已排序）是O(n) 空间复杂度： O(1)，只用了几个变量 稳定性： 稳定（相等的元素不会被交换）

冒泡排序在实际中几乎不用，因为它太慢了。但它的价值在于——帮你理解排序的本质是”比较和交换”。

三、选择排序——每次找最小的

思路

你整理一手扑克牌：从所有牌中找到最小的，放到最左边；再从剩下的牌中找到最小的，放到第二个位置……重复直到全部排完。

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

data = [64, 25, 12, 22, 11]
print(selection_sort(data))  # [11, 12, 22, 25, 64]

时间复杂度： 任何情况下都是O(n²)——即使数组已经排好，还是要扫描所有元素 空间复杂度： O(1) 稳定性： 不稳定（交换可能改变相等元素的相对顺序）

🤔 想一想 选择排序和冒泡排序都是O(n²)，但选择排序的交换次数最多n-1次，而冒泡排序最多交换n(n-1)/2次。这意味着什么？在交换代价很大的情况下（比如交换两个很大的对象），选择排序实际上可能更快。

四、插入排序——像整理手牌一样

思路

打扑克时你怎么整理手牌？拿到一张新牌，从右往左找到合适的位置插进去。插入排序就是这个过程。

def insertion_sort(arr):
    """插入排序"""
    for i in range(1, len(arr)):
        key = arr[i]  # 当前要插入的"新牌"
        j = i - 1
        # 把比key大的元素都往后挪一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # 把key放到正确位置
    return arr

data = [12, 11, 13, 5, 6]
print(insertion_sort(data))  # [5, 6, 11, 12, 13]

时间复杂度： 平均和最坏O(n²)，最好O(n) 空间复杂度： O(1) 稳定性： 稳定

插入排序虽然也是O(n²)，但在两个场景中意外地好用：

数据几乎有序时： 每个元素只需要移动很少的位置，接近O(n)
数据量很小时： n很小时，O(n²)和O(n log n)差距不大，而插入排序的常数系数更小

这就是为什么很多”混合排序”算法（如Timsort/Powersort、Introsort）在小规模数据上会切换到插入排序。

五、快速排序——分治思想的巅峰之作

思路

快速排序是实际中最常用的排序算法之一。它的思路像这样：

你是班主任，要给全班50个同学按身高排队。你选一个同学当”标杆”（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)

data = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(data))  # [1, 1, 2, 3, 6, 8, 10]

上面这个版本简洁易懂，但创建了额外的列表。下面是”原地”版本，不需要额外空间：

def quick_sort_inplace(arr, low=0, high=None):
    """原地快速排序"""
    if high is None:
        high = len(arr) - 1
    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)
    return arr

def partition(arr, low, high):
    """分区操作：把小于pivot的放左边，大于的放右边"""
    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

data = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort_inplace(data))  # [1, 1, 2, 3, 6, 8, 10]

时间复杂度： 平均O(n log n)，最坏O(n²) 空间复杂度： O(log n)（递归调用栈） 稳定性： 不稳定

快排为什么”最坏”会很慢？

如果每次选的pivot恰好是最大或最小值，分区就完全不均匀——一边0个元素，另一边n-1个。这样就退化成了O(n²)。

解决方法：

随机选pivot： 随机选一个元素而不是固定选第一个或最后一个
三数取中： 取第一个、最后一个、中间那个的中位数
对小规模数据切换到插入排序

六、归并排序——稳定可靠的分治方案

思路

归并排序也用分治策略，但思路和快排不同。它先把数组不断对半分，分到每组只有一个元素（一个元素自然是有序的），然后把有序的小组两两合并成更大的有序组。

就像你整理两摞已经按大小排好的扑克牌——每次比较两摞最上面的牌，较小的那张抽出来放到新的一摞里。

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

data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))  # [3, 9, 10, 27, 38, 43, 82]

时间复杂度： 任何情况下都是O(n log n)——分log(n)层，每层合并O(n) 空间复杂度： O(n)——需要额外数组存放合并结果 稳定性： 稳定

归并排序的性能很稳定，不像快排那样会退化。但它需要额外的O(n)空间。在需要稳定排序的场景中（比如数据库排序），归并排序是首选。

🤔 想一想 Python的内置排序（Timsort，Python 3.11起采用了改进的Powersort合并策略）结合了归并排序和插入排序的优点。你能猜到它是怎么结合的吗？（提示：先找到数组中已经有序的片段，然后用归并的方式合并这些片段）

七、堆排序——用堆的力量排序

思路

利用堆的特性：大顶堆的堆顶永远是最大的元素。每次把堆顶取出来放到数组末尾，再重新调整堆，重复直到堆为空。

def heap_sort(arr):
    """堆排序"""
    n = len(arr)

    def sift_down(start, end):
        """下沉操作"""
        parent = start
        while True:
            child = 2 * parent + 1
            if child > end:
                break
            if child + 1 <= end and arr[child + 1] > arr[child]:
                child += 1
            if arr[parent] >= arr[child]:
                break
            arr[parent], arr[child] = arr[child], arr[parent]
            parent = child

    # 第一步：建堆（从最后一个非叶节点开始下沉）
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n - 1)

    # 第二步：逐个取出堆顶
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 堆顶（最大值）放到末尾
        sift_down(0, i - 1)              # 调整剩余部分为堆

    return arr

data = [12, 11, 13, 5, 6, 7]
print(heap_sort(data))  # [5, 6, 7, 11, 12, 13]

时间复杂度： 任何情况下O(n log n) 空间复杂度： O(1)——原地排序 稳定性： 不稳定

堆排序是唯一一个同时做到O(n log n)时间和O(1)空间的排序算法。但实际使用中它通常比快排慢，因为它的数据访问模式对CPU缓存不友好。

八、排序算法大比武

算法	平均时间	最坏时间	空间	稳定	适用场景
冒泡排序	O(n²)	O(n²)	O(1)	稳定	教学、极小数据集
选择排序	O(n²)	O(n²)	O(1)	不稳定	交换代价大的场景
插入排序	O(n²)	O(n²)	O(1)	稳定	小规模、近乎有序的数据
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	通用场景，实际最快
归并排序	O(n log n)	O(n log n)	O(n)	稳定	需要稳定排序、外部排序
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	内存受限的场景

怎么选？

数据量小（<50）： 插入排序，简单高效
通用场景： 快速排序，实际表现最好
需要稳定性： 归并排序
内存紧张： 堆排序
数据几乎有序： 插入排序
不想操心： 用Python的sorted()——它基于Timsort（Python 3.11起将合并策略替换为Powersort），已经帮你做了最优选择

⚠️ 常见误区

误区1：“快排是最快的排序算法” —— 它的最坏情况是O(n²)。在需要保证性能下限的场景（如实时系统），归并排序或堆排序更可靠。

误区2：“O(n log n)是排序的极限” —— 这是基于比较的排序的下限。计数排序、桶排序、基数排序在特定条件下可以做到O(n)，因为它们不基于比较。

误区3：“排序算法的稳定性不重要” —— 当你按多个字段排序时（比如先按年龄再按姓名），稳定性就非常重要了。不稳定排序会打乱之前排好的顺序。

📝 掌握度自测

概念题： 什么是排序的”稳定性”？为什么它在某些场景下很重要？举一个具体的例子。
手算题： 用快速排序对 [5, 3, 8, 4, 2, 7, 1, 6] 排序，以第一个元素5为pivot，画出第一次分区后的结果。
分析题： 归并排序的空间复杂度为什么是O(n)而不是O(n log n)？（提示：虽然递归了log(n)层，但每层的临时数组用完就释放了。）
编码题： 实现一个函数，用快速排序的思路在O(n)平均时间内找到数组中第k大的元素（不需要排序整个数组）。
思考题： 如果你有100GB的数据需要排序，但内存只有4GB，你会怎么做？（提示：外部排序 + 归并）

💡 自我评估

全部答对：排序算法已经信手拈来了。

答对3-4题：核心理解到位，建议用不同大小的随机数组实际测试各种排序的运行时间。

答对1-2题：重新阅读快排和归并的思路部分，拿纸笔画出递归过程。

全部答错：排序是算法学习的重要一关，建议你先把冒泡和插入排序的代码完全理解，再挑战快排和归并。

排序解决的是”把数据排好队”的问题，而排好队之后最大的收益是什么？答案是：查找变快了。下一章我们来学习查找算法——特别是二分查找，它能在 100 万条有序数据中只用 20 次比较就找到目标。