排序

排序

排序是特化算法模块的起点，也是算法设计中最经典的问题之一。给定 $n$ 个元素的序列，排序算法将其重新排列，使得元素按某种序关系（通常为升序或降序）排列。

排序算法种类繁多，但它们并非彼此孤立。从基本思想出发，排序算法可以归入几个大的家族。本节按家族组织讨论，每个家族从最朴素的版本出发，逐步展开优化路径，最终抵达该家族中最具代表性的高效版本。

冒泡排序与快速排序：交换排序家族

交换排序家族的核心操作是比较并交换元素对。家族中最朴素的成员是冒泡排序，而快速排序则是将交换思想推向极致的优化版本。

冒泡排序

反复扫描序列，依次比较相邻元素。若它们的顺序不正确（前大于后），则交换二者。每一轮扫描会将当前未排序部分的最大元素“浮”到正确位置（如同气泡升至水面）。经过 $n-1$ 轮扫描后，整个序列有序。

function bubble_sort(A[0..n-1]):
    for i := 0 to n - 2:
        swapped := false
        for j := 0 to n - i - 2:
            if A[j] > A[j+1]:
                swap(A[j], A[j+1])
                swapped := true
        if not swapped:
            break

最坏时间复杂度：$O(n^2)$，发生在完全逆序时。
最好时间复杂度：$O(n)$，发生在已经有序时（检测到无交换后提前终止）。
空间复杂度：$O(1)$，原地排序。
稳定性：稳定，相等键值的元素不会交换。

快速排序

冒泡排序每次只将一个元素移动到正确位置，且单次交换只能纠正一个逆序对。快速排序的突破在于：一次操作将序列按某个主元划分为左右两部分，左边所有元素不大于主元，右边所有元素不小于主元。主元自此落位，左右子序列再递归执行同样操作。

这一“分而治之”的策略使得一次划分可以同时处理大量逆序对，效率远超冒泡。

function partition(A, low, high):
    pivot := A[high]            // 选取最后一个元素为主元
    i := low - 1                // i 指向小于区域的末尾
    for j := low to high - 1:
        if A[j] <= pivot:
            i := i + 1
            swap(A[i], A[j])
    swap(A[i + 1], A[high])     // 将主元放入正确位置
    return i + 1                // 返回主元最终位置

function quick_sort(A, low, high):
    if low < high:
        pi := partition(A, low, high)
        quick_sort(A, low, pi - 1)
        quick_sort(A, pi + 1, high)

最坏时间复杂度：$O(n^2)$，发生在每次划分极不平衡时（如主元恰好为最小或最大元素，常见于已有序序列选取固定位置主元）。
最好与平均时间复杂度：$O(n \log n)$，每次划分将序列均分为两半。
空间复杂度：$O(\log n)$ 至 $O(n)$，取决于递归栈的深度。
稳定性：不稳定，划分过程中的交换可能改变相等元素的相对顺序。

为了避免最坏情况，快速排序的实现通常包含一些优化策略：

三数取中法：选取 A[low]、A[mid]、A[high] 的中位数作为主元，降低最坏情况的出现概率。
三路划分：将序列分为小于、等于、大于主元三部分。当存在大量重复元素时，避免在相等区域反复递归。
小数组插入排序：当子数组长度小于某个阈值（通常为 10 至 20）时，改用插入排序，减少递归开销。
尾递归优化：只对较短的一侧递归，较长一侧用循环处理，将空间复杂度降至 $O(\log n)$。

冒泡与快排的关系

冒泡排序每一轮扫描实际上确定了未排序部分的极大值，这等价于选最后一个元素为主元，将所有小于它的元素浮到左侧，而它自身沉到底部。快速排序通过主动选择主元、双向交换、分治递归，将这一局部比较扩展为全局性的分治策略，从而将复杂度从 $O(n^2)$ 降至 $O(n \log n)$。冒泡的“逐对交换”被快排的“分区交换”所替代，交换思想从微观到了宏观。

选择排序与堆排序：选择排序家族

选择排序家族的核心操作是选择极值并将其归位。家族中最朴素的成员是直接选择排序，每次线性扫描未排序部分寻找最小元素。堆排序则用偏序树结构将这一选择过程从 $O(n)$ 优化至 $O(\log n)$。

选择排序

序列分为已排序部分（前缀）和未排序部分（后缀）。每轮从未排序部分中选出最小元素，与未排序部分的第一个元素交换，从而将已排序部分扩大一位。

function selection_sort(A[0..n-1]):
    for i := 0 to n - 2:
        min_idx := i
        for j := i + 1 to n - 1:
            if A[j] < A[min_idx]:
                min_idx := j
        if min_idx != i:
            swap(A[i], A[min_idx])

时间复杂度：始终为 $O(n^2)$，无论输入情况如何。每轮都必须扫描全部未排序元素。
空间复杂度：$O(1)$，原地排序。
稳定性：不稳定，交换可能破坏相等元素的相对顺序。

堆排序

选择排序的瓶颈在于每轮都需要 $O(n)$ 扫描来寻找最小值。堆排序用二叉堆替代线性扫描：先 $O(n)$ 建堆，此后每次获取并删除极值的代价仅为 $O(\log n)$。总共 $n$ 次删除，总复杂度 $O(n \log n)$。

时间复杂度：始终为 $O(n \log n)$。建堆 $O(n)$，每轮删除 $O(\log n)$。
空间复杂度：$O(1)$，原地排序。
稳定性：不稳定，堆的操作不保证相等元素的相对顺序。

选择与堆排的关系

选择排序每轮在无序部分做线性扫描选极值；堆排序将无序部分组织成堆，每次选极值只需 $O(\log n)$ 调整。两者的排序逻辑完全一致——每轮选出一个极值归位，区别仅在选择代价从 $O(n)$ 降至 $O(\log n)$。堆排序是选择思想与数据结构（堆）结合的典范，也是数据结构服务于算法的典型案例。

插入排序与希尔排序：插入排序家族

插入排序家族的核心操作是将元素插入到已排序前缀中的正确位置。家族中最朴素的成员是直接插入排序，希尔排序则通过“分组跳跃”大幅加速插入过程。

插入排序

将序列分为已排序前缀和未排序后缀。每次取未排序部分的第一个元素，在已排序前缀中从后向前扫描，找到其正确位置并插入。初始时，第一个元素自身构成已排序前缀。

function insertion_sort(A[0..n-1]):
    for i := 1 to n - 1:
        key := A[i]
        j := i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] := A[j]
            j := j - 1
        A[j + 1] := key

最坏时间复杂度：$O(n^2)$，发生在完全逆序时，每轮需移动全部已排序元素。
最好时间复杂度：$O(n)$，发生在已经有序时，每轮仅比较一次。
空间复杂度：$O(1)$，原地排序。
稳定性：稳定，相等元素不会越过彼此。

插入排序在小规模数据或基本有序的数据上表现极佳。它是快排和希尔排序在小数组上的常备辅助。

希尔排序

插入排序的痛点在于每次只移动一个位置——当一个元素距其正确位置很远时，需要大量逐次移动。希尔排序的突破在于：先用较大的步长（增量）将序列分为若干子序列，对每个子序列分别做插入排序。然后逐步缩小步长，重复操作。当步长最终为 $1$ 时，整个序列接近有序，最后一次插入排序的代价极低。

这一策略使得元素可以快速跨越较大距离移动，大幅削减了比较和移动的总次数。

function shell_sort(A[0..n-1]):
    n := length(A)
    gap := n / 2
    while gap > 0:
        for i := gap to n - 1:
            key := A[i]
            j := i
            while j >= gap and A[j - gap] > key:
                A[j] := A[j - gap]
                j := j - gap
            A[j] := key
        gap := gap / 2

时间复杂度：取决于步长序列。使用 Shell 原序列（$n/2$，$n/4$，$\dots$，$1$）时，最坏为 $O(n^2)$；使用 Hibbard 序列（$1$，$3$，$7$，$\dots$，$2^k-1$）时，最坏为 $O(n^{3/2})$；最优步长序列可达到 $O(n \log^2 n)$。平均性能在实践中通常优于 $O(n^{3/2})$。
空间复杂度：$O(1)$，原地排序。
稳定性：不稳定，分组跳跃可能改变相等元素的相对顺序。

插入与希尔的关系

希尔排序没有改变插入排序的核心操作——每一轮内层循环仍然是“从后向前找位置并逐次后移”。它只是改变了插入排序的外层调度策略：不是对全体元素依次插入，而是先用大步长让元素进行“长途跳跃”，再用小步长做精细调整。当步长退化为 $1$ 时，希尔排序退化为普通的插入排序。因此，希尔排序就是“分组跳跃的插入排序”，是插入思想的调度优化版本。

归并排序

归并排序代表的是另一条根本思路——分治与合并。它不依赖交换、选择或插入，而是将已有序的子序列逐层合并为更大的有序序列。

将序列递归地均分为两半，分别排序，然后将两个有序子序列合并为一个有序序列。递归的边界是序列长度为 $1$ 或 $0$，此时已自然有序。

function merge(A, left, mid, right):
    n1 := mid - left + 1
    n2 := right - mid
    L[0..n1-1] := A[left..mid]
    R[0..n2-1] := A[mid+1..right]
    i := 0; j := 0; k := left
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            A[k] := L[i]; i := i + 1
        else:
            A[k] := R[j]; j := j + 1
        k := k + 1
    while i < n1:
        A[k] := L[i]; i := i + 1; k := k + 1
    while j < n2:
        A[k] := R[j]; j := j + 1; k := k + 1

function merge_sort(A, left, right):
    if left < right:
        mid := (left + right) / 2
        merge_sort(A, left, mid)
        merge_sort(A, mid + 1, right)
        merge(A, left, mid, right)

时间复杂度：始终为 $O(n \log n)$，无论输入情况。归并树层数为 $O(\log n)$，每层合并代价 $O(n)$。
空间复杂度：$O(n)$，需要辅助数组存储临时合并结果。
稳定性：稳定，合并时若相等元素取左侧优先，相对顺序不变。

归并排序是稳定的 $O(n \log n)$ 算法，特别适合排序链表（因为链表可以 $O(1)$ 合并而无额外空间开销），也广泛用于外部排序——当数据量大到无法一次装入内存时，归并排序的分治合并策略可以自然地扩展到多路归并。

桶排序、计数排序与基数排序：分布排序家族

分布排序家族的核心思想是将元素分配到不同的桶中，再对桶内排序后合并。它们不基于比较，因此可以突破比较排序的 $O(n \log n)$ 下界。

桶排序

假设输入数据均匀分布在一定范围内。将这一范围划分为若干个等大的区间（桶），将每个元素放入对应桶中。对每个桶内进行排序（通常用插入排序或其他简易排序），最后将所有桶中的元素按顺序输出。

function bucket_sort(A[0..n-1]):
    n := length(A)
    创建 n 个空桶
    for i := 0 to n - 1:
        将 A[i] 放入对应的桶中
    for each bucket:
        对桶内元素进行排序（通常用插入排序）
    将所有桶中的元素按顺序连接回原数组

时间复杂度：期望 $O(n)$，最坏 $O(n^2)$（所有元素落入同一桶）。
空间复杂度：$O(n)$，需要额外的桶空间。
稳定性：取决于桶内排序算法的稳定性。

计数排序

桶排序在键值为非负整数且范围较小时的退化情形。统计每个键值出现的次数（计数），然后依次输出相应数量的该键值。由于计数数组直接充当了桶的角色，无需桶内再排序。

function counting_sort(A[0..n-1], max_val):
    count[0..max_val] := {0}
    for i := 0 to n - 1:
        count[A[i]] := count[A[i]] + 1
    idx := 0
    for val := 0 to max_val:
        for _ := 1 to count[val]:
            A[idx] := val
            idx := idx + 1

时间复杂度：$O(n + k)$，$k$ 为值域大小（$k = \max_val$）。
空间复杂度：$O(n + k)$。
稳定性：上述输出方式稳定。若仅做计数无需保持稳定，则前缀和优化可使其原地输出。
局限性：仅适用于值域范围较小的非负整数。

基数排序

当键值的值域太大使得计数排序不可行时，基数排序提供了一条出路：按位排序。将键值视为定长序列（如整数按进制分解为多个数位，字符串为字符序列），从最低位到最高位（LSD）或从最高位到最低位（MSD），依次对每一位进行一次稳定的排序（通常用计数排序作为稳定子排序）。

function radix_sort(A[0..n-1]):
    max_val := max(A)
    exp := 1
    while max_val / exp > 0:
        counting_sort_by_digit(A, exp)   // 对当前位做稳定计数排序
        exp := exp * 10

counting_sort_by_digit 根据键值除以 exp 取余数再除以 exp 得到当前位的数值，对该位执行稳定的计数排序。

时间复杂度：$O(d \cdot (n + k))$，$d$ 为位数，$k$ 为每位的基数（如十进制下 $k=10$）。
空间复杂度：$O(n + k)$。
稳定性：若每位排序是稳定的，则基数排序整体稳定。

桶、计数、基数三者的关系

计数排序是桶排序的特例——每个可能的键值就是一个桶。基数排序则是计数排序的多次分层应用——每次只按键值的一个数位进行计数排序，通过从低位到高位的稳定排序，最终完成全键排序。三者共享同一个本质：将元素按照键值特性分配到有限类别中，再集中输出。这正是“分布”的含义。

排序算法总结

排序算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	家族
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	交换
快速排序	$O(n \log n)$	$O(n^2)$	$O(\log n)$	不稳定	交换
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	选择
堆排序	$O(n \log n)$	$O(n \log n)$	$O(1)$	不稳定	选择
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	插入
希尔排序	约 $O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定	插入
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n)$	稳定	归并
桶排序	$O(n)$	$O(n^2)$	$O(n)$	取决于内排序	分布
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定	分布
基数排序	$O(d \cdot (n+k))$	$O(d \cdot (n+k))$	$O(n+k)$	稳定	分布

这一排序算法家族谱系，展示了算法设计中最核心的几类优化策略：从冒泡到快排是分治优化，从选择到堆排是数据结构优化，从插入到希尔是调度优化，归并是合并优化，而基数等分布排序是改变比较模型的突破。每一组“基本算法→优化版本”的对应，都是算法思想演进的缩影，也为后续图论、字符串等领域的算法设计提供了思考原型。

最近更新文章

编程导论：2.1.特化算法

特化算法介绍

排序