第 9 章 排序

Sorting

引入

假设数据库要处理一张包含 1000 万行记录的表：

SELECT * FROM records ORDER BY key;

ORDER BY key 要求执行器产生按关键码（key）全局有序的结果；排序因此是查询执行计划的一部分，而不是孤立算法。

真实系统会结合数据规模、可用内存、稳定性（stability）要求，以及是否只需要前 N 条结果来选择具体排序策略。

如果只问一句“哪种排序最快”，答案并不可靠，因为执行环境可能完全不同：

• 输入数据已经基本有序
• 相同关键码的记录需要保持原有相对顺序
• 可用内存很小
• 查询实际只需要 ORDER BY ... LIMIT 100

条件一变，数据库执行器选择的策略也会跟着变。

排序的核心问题：根据数据特征、数据规模、可用内存以及实际目标，选择总体代价合适的方法。

排序问题几乎出现在所有数据处理系统里

同一种需求会以不同形式出现：

• 成绩系统：按总分排序，同时保持同分学生的原始顺序
• 数据库：ORDER BY、只取前 N 条记录和归并连接（merge join）都依赖排序
• 日志处理：大量记录按时间戳（timestamp）整理，甚至需要外排序（external sorting）
• 智能体工具选择：当系统为多个候选工具或动作计算得分后，常需要先选出得分最高的前 K 个候选，再决定实际尝试哪些

这些例子共同提出了一组比“升序还是降序”更重要的问题：比较多少次、移动多少次、需要多少额外空间、是否稳定、是否利用已有有序性，以及数据规模是否超过内存。

本章因此不会把算法看成孤立技巧，而是围绕插入、交换、选择、归并、分配等不同策略，建立一套排序算法的选择框架。

学习目标

• 掌握排序的稳定性、内排序（internal sorting）、外排序和评价维度
• 掌握直接插入排序（straight insertion sort）、折半插入排序（binary insertion sort）、希尔排序（Shell sort）
• 掌握冒泡排序（bubble sort）和快速排序
• 掌握直接选择排序（selection sort）、锦标赛排序（tournament sort）和堆排序（heap sort）
• 掌握归并排序（merge sort）和链表归并排序
• 理解基数排序（radix sort）的思想
• 能比较各类排序算法的时间、空间、稳定性和适用场景

本章路线图

排序
Sorting

评价框架
时间 · 空间 · 稳定性 · 输入敏感性 插入类
直接插入 · 折半插入 · 希尔 交换类
冒泡 · 快速排序 选择类
直接选择 · 锦标赛 · 堆排序 归并类
分治 · 顺序表与链表归并 分配类
基数排序 · 不依赖比较 算法选型
数据规模 · 分布 · 工程约束

先明确排序的对象：记录与关键码

真正被排序的通常不是一串孤立数字，而是一组完整记录。每条记录包含：

• 关键码（key）：决定两条记录谁排在前面；
• 其它字段：必须始终跟着这条记录一起移动。

因此，后面讨论“交换”“移动”和“稳定性”时，指的都是完整记录，而不只是屏幕上显示的关键码。

record Record<Key extends Comparable<? super Key>, Value>(Key key, Value value) implements Comparable<Record<Key, Value>> {
    @Override
    public int compareTo(Record<Key, Value> other) {
        return key.compareTo(other.key);
    }
}

Record 把关键码和附带数据绑定成一个整体；排序过程中二者不能分开移动。

compareTo(…) 定义两条记录怎样比较；这里比较依据只有关键码。

关键码相等时 compareTo 返回 0；这些记录最终是否保持原来的先后顺序，要由具体排序算法决定。

评价框架

排序评价维度

维度	含义
比较次数	关键码之间比较的次数
移动次数	记录移动或交换次数
时间复杂度	最好、最坏、平均
空间复杂度	是否需要额外数组或递归栈
稳定性	相等关键码的相对顺序是否保持
原地性（in-place）	是否只使用 \(O(1)\) 或少量额外空间
输入敏感性	是否利用已有有序性

稳定性

若两个对象的关键码相等，排序前后它们的相对顺序保持不变，则排序算法稳定。

例如：

\[ 25_a,\ 18,\ 25_b,\ 10 \]

稳定排序后：

\[ 10,\ 18,\ 25_a,\ 25_b \]

不稳定排序可能得到：

\[ 10,\ 18,\ 25_b,\ 25_a \]

内排序与外排序

内排序：所有待排序记录都能放入内存。

外排序：数据规模超过内存，需要访问外存。

本章主要讨论内排序。

外排序的核心通常是多路归并和缓冲区管理。

插入排序

直接插入排序思想

设第 \(i\) 轮开始时，\(R[0],R[1],\ldots,R[i-1]\) 已经有序。

先把 \(R[i]\) 暂存起来，在有序前缀中寻找它应该插入的位置；比它大的记录逐个右移，空位一路向左移动，最后再把暂存记录放进空位。

直接插入排序代码

static <T extends Comparable<? super T>> void insertionSort(T[] a) {
    for (int p = 1; p < a.length; p++) {
        T tmp = a[p];
        int j = p;
        while (j > 0 && tmp.compareTo(a[j - 1]) < 0) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = tmp;
    }
}

insertionSort(…) 逐个扩展有序前缀；每次把新元素插入它在前缀中的正确位置。

第 p 轮开始时，a[0..p-1] 已经有序；先暂存 a[p]，等价于在有序前缀右侧开出一个待安放的元素。

只要前一个元素严格大于 tmp，就把它右移一格并让空位向左推进；相等时不移动，因此已有相等记录不会被新记录跨过，排序保持稳定。

把 tmp 写入最终空位后，有序前缀从长度 p 扩大到 p+1；近乎有序时接近 O(n)，最坏 O(n²)，只用 O(1) 额外空间且保持稳定。

直接插入排序适合小规模数据，也特别适合已经基本有序的数据。

折半插入排序

折半插入排序只优化一件事：在已经有序的左侧区间里，用二分查找更快地确定插入位置。 找到位置以后，数组仍然必须把这一位置之后的元素整体右移。

动画使用 [12,5,9,2,14,7,1,10,6]。从第 1 轮开始就会发生真正的插入：先把 5 从下标 1 取出，在左侧有序前缀 [12] 中确定位置，再把 12 右移。随着有序前缀变长，二分查找才会逐渐体现“把候选区间一半一半缩小”的作用。

折半插入排序代码

static <T extends Comparable<? super T>> void binaryInsertionSort(T[] a) {
    for (int p = 1; p < a.length; p++) {
        T tmp = a[p];
        int left = 0;
        int right = p;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tmp.compareTo(a[mid]) < 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        for (int j = p; j > left; j--) {
            a[j] = a[j - 1];
        }
        a[left] = tmp;
    }
}

binaryInsertionSort(…) 用二分查找确定插入位置，再搬移区间；比较次数下降，但搬移仍可能是线性的。

第 p 轮仍把 a[p] 插入有序前缀，只是先把候选插入位置设为半开区间 [left,right)；这里 right=p 明确排除尚未归位的 tmp。

二分每次砍掉一半候选位置；相等时让 left=mid+1，把新记录放到已有相等记录之后，这是折半插入仍能保持稳定性的关键。

找到 left 后，数组并不会因为“查找更快”就免于搬移：仍需把 a[left..p-1] 整体右移一格，为 tmp 腾出槽位。

写回 tmp 后本轮前缀重新有序；比较次数降到 O(n log n) 量级，但移动最坏仍是 O(n²)，所以总时间仍 O(n²)；额外空间 O(1)，且右侧插入规则保持稳定。

希尔排序思想

直接插入排序每次只能让记录向左或向右移动一格

如果一个很小的记录一开始离目标位置很远，就要经过很多次搬移。希尔排序先用较大的间隔做“远距离插入”，再逐步缩小间隔。

不同轮次间隔的规则：

\[ gap_0=\left\lfloor\frac{n}{2}\right\rfloor,\qquad gap_{k+1}=\left\lfloor\frac{gap_k}{2}\right\rfloor \]

直到 gap=1。动画有 12 个元素，所以 gap 依次为 6 → 3 → 1。

每个 gap 下，把下标相差 gap 的记录看成同一条子序列，并在这条子序列上执行插入排序

最后 gap=1 时就是一次普通插入排序，此时完成整体排序。

希尔排序图解：先大步调整，再逐步缩小 gap

希尔排序代码

static <T extends Comparable<? super T>> void shellSort(T[] a) {
    for (int gap = a.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < a.length; i++) {
            T tmp = a[i];
            int j = i;
            while (j >= gap && tmp.compareTo(a[j - gap]) < 0) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = tmp;
        }
    }
}

shellSort(…) 按逐渐缩小的间隔做分组插入，最终在 gap=1 时完成整体排序。

每一轮都把数组看成若干条等间隔子序列；间隔逐步缩小，使元素先用大步长跨越远距离逆序，最后再以间隔 1 完成整体整理。

对当前子序列执行跨间隔插入：比 tmp 大的前驱向后搬一个间隔，空位沿同一条子序列向左移动，直到 tmp 能保持这条子序列有序。

写回 tmp 后当前间隔子序列恢复有序；跨距离移动可能越过相等关键码，所以希尔排序通常不稳定。性能取决于增量序列；本实现反复把增量减半，最坏仍为 O(n²)，额外空间 O(1)。

不同的增量序列会显著影响希尔排序的性能。

交换排序

冒泡排序

冒泡排序从左到右反复比较相邻记录，只有顺序颠倒时才交换。一次完整扫描结束后，当前未排序区中的最大记录一定被推到最右端，因此右侧“已经确定”的区间会一趟一趟扩大。

冒泡排序代码

static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    for (int n = a.length; n > 1; n--) {
        boolean swapped = false;
        for (int i = 1; i < n; i++) {
            if (a[i].compareTo(a[i - 1]) < 0) {
                T tmp = a[i];
                a[i] = a[i - 1];
                a[i - 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

bubbleSort(…) 反复执行相邻逆序交换；每一趟都会把一个极值固定到已排序边界。

每一趟只处理尚未确定的前缀 [0,n)；上一趟已经把一个最大元素送到右端，所以有序后缀不断扩大，本趟先把 swapped 重置为 false。

从左到右只交换严格逆序的相邻记录；最大值会被连续推向本趟末端，而相等记录不会互换，因此冒泡排序保持稳定。

若整趟没有发生任何交换，当前前缀本来就已经有序，可以提前结束；最好 O(n)，平均/最坏 O(n²)，额外空间 O(1)；只交换严格逆序的相邻记录，因此稳定。

快速排序思想

快速排序先不追求“一步把整个数组排好”，而是先解决一个更小的问题：选一个枢轴（pivot），把它放到最终位置，并把其余记录分到枢轴两侧。 本课的划分规则是：

1. 选择最右端记录作为枢轴；
2. 从左到右扫描，其间维护“\(\le\) 枢轴”的左区；
3. 扫描结束后，把枢轴放到左区与右区的分界位置；
4. 枢轴已经永久确定，左右两个子区间再分别重复同样的过程。

关键点是：一次划分只保证枢轴位置正确，并不保证左右两边各自已经有序。

快速排序图解：先看懂一次划分

划分结束后为什么还要递归

一次划分结束后，枢轴左侧都不大于它，右侧都大于它，但左右区间内部仍可能是乱序的。因此快速排序把这两个更小的区间当成两个同类问题，继续划分；区间缩到 0 个或 1 个记录时自然结束。

快速排序：划分（partition）

static <T extends Comparable<? super T>> int partition(T[] a, int left, int right) {
    T pivot = a[right];
    int store = left;
    for (int i = left; i < right; i++) {
        if (a[i].compareTo(pivot) <= 0) {
            T tmp = a[store];
            a[store] = a[i];
            a[i] = tmp;
            store++;
        }
    }
    T tmp = a[store];
    a[store] = a[right];
    a[right] = tmp;
    return store;
}

partition(…) 要把枢轴放到最终位置，并保证它左侧不大于枢轴、右侧大于枢轴。

先把最右元素选作枢轴，并令 store=left；此后 a[left..store-1] 始终表示已经确认“不大于枢轴”的左区。

扫描未分类元素时，只有 a[i] ≤ 枢轴 才交换到 store 并扩张左区；因此循环结束时左侧全都 ≤ 枢轴，尚未归入左区的元素全都大于枢轴。

最后把枢轴放到 store，枢轴才处于最终下标；这种跨距离交换可能越过相等记录，因此这种原地划分通常不稳定。

划分完成后，枢轴位于最终位置。

快速排序代码

static <T extends Comparable<? super T>> void quickSort(T[] a) {
    quickSortRange(a, 0, a.length - 1);
}

private static <T extends Comparable<? super T>> void quickSortRange(
        T[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = partition(a, left, right);
    quickSortRange(a, left, pivot - 1);
    quickSortRange(a, pivot + 1, right);
}

quickSort(…) 通过划分固定一个枢轴，再递归处理左右两个互不重叠的子区间。

公开入口只把整段数组交给统一的区间递归；排序过程中始终使用闭区间 [left,right]，因此空区间和单元素区间都由同一个递归终止条件收住。

当 left < right 时才需要划分；划分返回的枢轴已在最终位置，所以它本身不再参加任何后续递归。

只递归两个严格更小且互不重叠的区间；均衡/平均情况下时间 O(n log n)、栈深 O(log n)，长期选择极端枢轴会退化到 O(n²) 与 O(n) 栈。划分过程原地完成但通常不稳定。

工程实现还常加入三数取中、小数组改用插入排序、随机选择枢轴、减少递归深度等优化。

选择排序

直接选择排序

第 \(i\) 趟只做一件事：完整扫描未排序区间，记住其中最小记录的位置；扫描结束后，再把这个最小记录放到位置 \(i\)。与冒泡排序不同，它不会在扫描过程中反复交换。

直接选择排序代码

static <T extends Comparable<? super T>> void selectionSort(T[] a) {
    for (int i = 0; i + 1 < a.length; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j].compareTo(a[min]) < 0) {
                min = j;
            }
        }
        T tmp = a[i];
        a[i] = a[min];
        a[min] = tmp;
    }
}

selectionSort(…) 每轮把未排序区的最小元素放到边界位置，并逐步扩大已确认有序前缀。

第 i 轮开始时，前缀 a[0..i-1] 已经是最终结果；本轮只需在未排序后缀中确定“谁应该永久放到位置 i”。

完整扫描 i..end 并维护当前最小位置 min；无论输入是否已有序，都必须看完这个后缀，因此比较次数固定为 O(n²)。

只做一次远距离交换把最小值送到 i，移动次数因此较少；额外空间 O(1)，但比较仍是 Θ(n²)。远距离交换可能跨过相等关键码，所以直接选择排序通常不稳定。

锦标赛排序

如果每次找最小值都从头扫描剩余记录，就会重复做很多已经知道结果的比较。锦标赛排序把比较过程保存成一棵“比赛树”：两个记录先两两比较，较小者晋级；再让各组胜者继续比较，最后根结点得到全局最小值。

输出最小值后，只需要让它原来经过的那条路径重新比赛，其它分支的比较结果可以继续使用。

锦标赛排序分析

建立锦标赛树（tournament tree）需要 \(O(n)\) 次比较；每输出一个最小值后，只需要沿着该元素原来经过的路径重赛，路径高度为 \(O(\log n)\)。

如果要输出全部 \(n\) 个元素，总时间复杂度为 \(O(n\log n)\)；如果只需要最小值或前若干小值，它的比较复用更有意义。

锦标赛树本身需要 \(O(n)\) 额外空间，所以数组版本不是原地排序。稳定性取决于胜负规则和是否保留原始位置作为平局判定依据；若只保存关键码而不处理相等关键码的先后，不能默认稳定。

堆排序

堆排序直接复用第 6 章学过的最大堆：堆顶始终是当前堆区中的最大记录。

流程：

1. 用自底向上的下滤方法建立最大堆（也称 Floyd 建堆法）；
2. 交换堆顶和当前堆区的最后一个记录，把最大值放到最终位置；
3. 堆区长度减一，右侧有序区扩大；
4. 从根结点向下调整，恢复最大堆；
5. 重复，直到堆区只剩一个记录。

堆排序代码

static <T extends Comparable<? super T>> void heapSort(T[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        percolateDown(a, i, a.length);
    }
    for (int end = a.length - 1; end > 0; end--) {
        T tmp = a[0];
        a[0] = a[end];
        a[end] = tmp;
        percolateDown(a, 0, end);
    }
}

private static <T extends Comparable<? super T>> void percolateDown(T[] a, int hole, int size) {
    T tmp = a[hole];
    while (hole * 2 + 1 < size) {
        int child = hole * 2 + 1;
        if (child + 1 < size && a[child].compareTo(a[child + 1]) < 0) {
            child++;
        }
        if (tmp.compareTo(a[child]) >= 0) {
            break;
        }
        a[hole] = a[child];
        hole = child;
    }
    a[hole] = tmp;
}

heapSort(…) 维护一个最大堆，把堆顶最大值逐个交换到数组尾部的已排序区。

从最后一个内部结点开始，依次向前对各子树做下滤；叶结点天然满足堆序，因此不必处理。这个自底向上的 Floyd 建堆过程总成本是 O(n)。

每轮把根部最大值交换到 end，右侧已排序后缀扩大一格；随后只在缩短后的堆区间 [0,end) 恢复堆序。

percolateDown(…) 只修复从指定结点向下的一条堆序路径，使该子树重新满足堆不变量。

下滤只需要沿一条路径前进：先在左右孩子中选较大的那个，因为只有它最有可能违反“父结点 ≥ 两个孩子”的最大堆条件。

若暂存值已经不小于最大孩子，当前位置直接满足堆序；否则把孩子上移填洞，并让 hole 沿这条路径继续下降。

把暂存值写入最终 hole 后堆序恢复；排序阶段做 n-1 次 O(log n) 下滤，总时间 O(n log n)，原地但不稳定。

归并排序

归并排序思想

归并排序抓住一个简单事实：两个已经有序的序列，可以只比较两边当前最小的记录，线性地合并成一个更长的有序序列。 因此整体思路是先把大问题拆小，等小区间各自有序后，再一层一层合并回来。

递归版本可以概括为：

1. 把当前区间分成左右两半；
2. 分别把左右两半排好；
3. 合并两个已经有序的子区间。

归并排序图解：有序段怎样逐层变长

归并排序递归结构

动画用自底向上的方式展示“有序段从长度 1 逐步合并成 2、4、8”；递归实现虽然执行顺序不同，但最终完成的是同一批“合并两个有序区间”的操作。

合并两个有序区间

static <T extends Comparable<? super T>> void merge(T[] a, T[] tmp,
                                                    int left, int right, int rightEnd) {
    int leftEnd = right - 1;
    int pos = left;
    int start = left;
    while (left <= leftEnd && right <= rightEnd) {
        if (a[left].compareTo(a[right]) <= 0) {
            tmp[pos++] = a[left++];
        } else {
            tmp[pos++] = a[right++];
        }
    }
    while (left <= leftEnd) {
        tmp[pos++] = a[left++];
    }
    while (right <= rightEnd) {
        tmp[pos++] = a[right++];
    }
    for (int i = start; i <= rightEnd; i++) {
        a[i] = tmp[i];
    }
}

输入的左右区间已经分别有序；先固定左段末尾、输出位置和原始起点，后续只需维护“两边尚未消费的队头”。

主循环每次取两个队头中较小者写入 tmp；相等时用 ≤ 优先取左段记录，因此跨两段的相等关键码仍保持原相对顺序。

一边耗尽后，另一边剩余部分本来就有序，可直接顺序搬完；整个合并过程对当前区间只做线性工作。

最后把 tmp 中的合并结果复制回原区间；数组版归并排序因而需要 O(n) 辅助空间，而稳定性来自前一步“相等时优先取左段”的规则。

相等时优先取左边元素，保证稳定性。

递归归并排序

static <T extends Comparable<? super T>> void mergeSort(T[] a) {
    T[] tmp = Arrays.copyOf(a, a.length);
    mergeSortRange(a, tmp, 0, a.length - 1);
}

private static <T extends Comparable<? super T>> void mergeSortRange(
        T[] a, T[] tmp, int left, int right) {
    if (left >= right) {
        return;
    }
    int center = left + (right - left) / 2;
    mergeSortRange(a, tmp, left, center);
    mergeSortRange(a, tmp, center + 1, right);
    merge(a, tmp, left, center + 1, right);
}

mergeSort(…) 递归把区间分成两半并稳定合并两个有序子区间。

入口只分配一次与数组同长的辅助区，并把整个闭区间交给递归；所有递归层共享这块 tmp，避免每层重复申请线性空间。

空区间和单元素区间天然有序，直接返回；这既是递归终止条件，也保证真正进入分治的区间至少含两个元素。

当前区间二分后，先递归排好左右两半，再合并成一个有序区间；每层总合并工作为 O(n)、层数 O(log n)，因此总时间稳定在 O(n log n)。

递归深度为 \(O(\log n)\)；每一层的合并总成本为 \(O(n)\)。

迭代归并排序

迭代归并从长度 1 的有序段开始：

\[ [1]\to[2]\to[4]\to[8]\to\cdots \]

每一趟把相邻的两个有序段合并为更长的有序段。

迭代版避免递归调用，但仍需要辅助数组。

链表归并排序

数组归并需要把记录写入辅助数组，再复制回原数组；链表没有这种连续存储限制。合并两个有序链表时，只要比较两个头结点，并把较小的那个结点接到结果链表尾部即可，原链表中其它结点不需要整体搬移。

链表不适合随机访问，却很适合这种“从头到尾顺序合并”的过程：合并时主要重连指针，不需要像数组那样整体搬移一段记录。

链表归并排序分析

链表归并排序常用于链表结构；它同样有 \(O(\log n)\) 层递归，每层只顺序扫描并重连结点一次，因此最好、平均、最坏时间复杂度都是 \(O(n\log n)\)。

合并两个链表时不需要数组辅助区，主要额外成本是递归栈 \(O(\log n)\)；若用自底向上（bottom-up）的迭代归并，还可以把栈空间降到 \(O(1)\)。但它不是数组意义上的原地排序：它依赖链表结点和指针重连，而不是在连续数组中原地交换。

只要相等关键码时优先取左链表结点，链表归并排序稳定。

分配排序

为什么比较排序很难再突破 \(n\log n\)？

到这里学过的插入、交换、选择、堆和归并排序，都要通过“比较两个关键码”来判断谁应该排在前面。一个自然的问题是：能不能设计出一种通用的比较排序，把最坏比较次数降到 \(O(n)\)？

只通过两两比较决定顺序的排序过程，可以抽象成一棵二叉决策树：每个内部结点代表一次比较，两条分支代表比较的两种结果，每个叶结点对应一种最终排列。

长度为 \(n\) 的输入共有 \(n!\) 种可能排列，所以决策树至少需要 \(n!\) 个叶结点。若最坏情况下经过 \(h\) 次比较，二叉决策树最多容纳 \(2^h\) 个叶结点，因此必须有 \(2^h \ge n!\)，从而得到 \(h \ge \log_2(n!) \approx n\log n\)。

这说明：在只靠比较决定顺序的模型里，通用排序的最坏比较次数不可能低于 \(O(n\log n)\)。 这并不是说所有排序都受这个下界限制；如果关键码本身还有可以利用的结构，就可能绕开“两两比较”。

能不能不比较完整关键码？

十进制整数天然由个位、十位、百位等数位组成。

与其反复问“这两个整数谁更小”，我们也可以利用这些数位，把记录直接分配到若干桶里。

基数排序就是沿着这条思路工作。

基数排序不属于比较排序。

基数排序思想

不直接比较两个完整关键码，而是按关键码的各个数位反复“分配到桶中，再按桶号收集”。

以低位优先（LSD）的十进制整数排序为例：先按个位稳定分桶并收集，再按十位、百位继续处理。

每一趟都必须保持同一桶中记录原来的先后顺序，否则前一趟已经建立的低位次序会被破坏。

基数排序图解：按个位、十位、百位逐趟分配和收集

基数排序的成本与适用条件

若关键码位数为 \(d\)，基数为 \(r\)，元素数为 \(n\)，每一趟分配和收集成本为 \(O(n+r)\)，共 \(d\) 趟：

\[ O(d(n+r)) \]

基数排序需要桶、计数或输出数组，空间复杂度通常为 \(O(n+r)\)，不是原地排序。

稳定性不是附带性质，而是正确性条件：低位优先基数排序（Least Significant Digit Radix Sort，LSD 基数排序）必须让每一趟分配保持上一趟已经建立的低位顺序。因此基数排序通常使用稳定的分桶或计数过程。

它适合定长整数或字符串；若 \(d\) 很大、关键码长短不齐或需要复杂比较函数，优势会下降。

比较与选型

排序算法回顾

前面已经逐个分析了每种算法，复习时不要只背结论，先问四个问题：

• 输入是否接近有序？这会明显影响插入排序和带提前结束的冒泡排序。
• 是否必须稳定？若必须稳定，优先考虑插入、归并或稳定的分配排序。
• 额外空间是否受限？数组归并和基数排序需要明显辅助空间，堆排序和多数插入/选择类算法更节省空间。
• 最坏情况是否重要？若最坏复杂度必须稳定在 \(O(n\log n)\)，堆排序和归并排序比普通快速排序更可靠。

工程连接：真实排序库为什么不会只用一种算法

学完前面的具体算法后，再回来看工程实现就容易理解了：真实系统通常会根据数据类型、数据规模和运行环境组合多种策略，而不是固定使用某一种课堂算法。

Java 标准库 标准库会按数据类型选择工程化实现；课程代码只展示各算法最核心的机制

Python Timsort 会利用输入中已经存在的有序段，减少不必要的工作

PostgreSQL 外排序和只取前 N 条记录时，会同时考虑内存、磁盘和执行计划

系统工具 大文件无法一次装入内存时，常采用分块排序、缓冲区和多路归并

所以工程选型不能只看一个 \(O(\cdot)\)：还要同时考虑稳定性、额外空间、输入是否接近有序、递归深度以及数据是否能全部放入内存。

如何选择排序算法

场景	推荐
小数组或基本有序	插入排序
通用内存排序	快速排序
需要稳定性	归并排序
空间受限且不要求稳定	堆排序
链表排序	归并排序
整数关键码位数受限	基数排序
只取最大的或最小的前 K 个结果	堆

本章小结

• 排序评价不能只看升序结果，还要同时检查稳定性、内外存条件、比较次数、移动次数和额外空间。
• 插入类排序逐步扩大有序前缀；直接插入、折半插入和希尔排序分别改变查找位置或移动跨度。
• 交换类排序通过相邻交换或划分调整相对位置；冒泡强调局部交换，快速排序强调分治划分。
• 选择类排序每轮选出极值；直接选择、锦标赛和堆排序在辅助信息与调整成本上取舍不同。
• 归并排序把有序子序列合并成更长有序序列，数组实现需要辅助空间，链表实现更适合重连节点。
• 基数排序不依赖比较下界，而是利用关键码的位或桶结构按多轮分配与收集处理数据。
• 选择排序算法时，要把时间、空间、稳定性、输入有序程度、数据规模和应用场景放在同一个框架中比较。

下载本章完整 Gradle 工程

本章习题

• 习题 1：插入排序：对序列 \(3,1,4,1,5,9,2,6,5\) 执行直接插入排序，写出关键趟后的序列并给出最终结果。
• 习题 2：第二趟排序结果判断：序列 \(11,12,13,7,8,9,23,4,5\) 是某种排序执行第二趟后的结果。判断最可能是哪种排序，并说明依据。
• 习题 3：归并排序：对序列 \(3,1,4,1,5,9,2,6\) 执行归并排序，写出分解与逐层合并过程。
• 习题 4：堆排序稳定性：判断堆排序是否稳定，并从堆调整过程中相等关键码的相对位置变化解释原因。

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦