第八章 排序

8.1 排序的基本概念

排序：将一组无序数据按照关键字递增（或递减）排列。

稳定性：若排序前两个相等的元素 $R_i$ 和 $R_j$（$i < j$），排序后 $R_i$ 仍在 $R_j$ 前面，则称排序算法是稳定的，否则是不稳定的。

🗣️ 大白话：假设班里有两个学生都叫"张三"，排序前 A张三 在 B张三 前面。如果排序后 A张三 还在前面，这种排序就是"稳定"的。

内部排序 vs 外部排序：

• 内部排序：数据全部在内存中
• 外部排序：数据量大，需借助外存

🔗 【跨学科联动·OS/计组】 排序算法的选择与 OS 和计组紧密关联：

• OS·外部排序：当数据无法全部装入内存时，需要利用 OS 的文件系统和缓冲区管理进行外部归并排序。归并路数受内存缓冲区数量限制
• OS·虚拟内存：排序时若访问模式不佳（如快排的随机跳转访问），可能导致大量缺页中断，严重影响性能
• 计组·Cache 友好性：归并排序的顺序访问模式比快排的随机访问更Cache 友好，但快排的常数因子更小。实际工程中常在小规模子问题切换为插入排序以提升 Cache 命中率
• OS·进程调度：优先级队列调度本质就是用堆排序的思想——每次取出优先级最高的进程执行

8.2 插入排序

一、直接插入排序

思想：将待排序元素插入到已排好的有序子序列中的适当位置。

void InsertSort(ElemType A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {      // 从第2个元素开始
        if (A[i] < A[i-1]) {        // 若当前元素小于前驱
            A[0] = A[i];            // 复制为哨兵
            for (j = i - 1; A[0] < A[j]; j--)
                A[j+1] = A[j];      // 记录后移
            A[j+1] = A[0];          // 复制到插入位置
        }
    }
}

// 直接插入排序（Java版，下标从0开始）
void insertSort(int[] A, int n) {
    for (int i = 1; i < n; i++) {
        if (A[i] < A[i - 1]) {
            int temp = A[i];
            int j;
            for (j = i - 1; j >= 0 && temp < A[j]; j--)
                A[j + 1] = A[j];   // 记录后移
            A[j + 1] = temp;        // 复制到插入位置
        }
    }
}

二、折半插入排序

思想：在直接插入排序的基础上，用折半查找来确定插入位置（减少比较次数，但移动次数不变）。

void InsertSort_Binary(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        A[0] = A[i];             // 暂存到哨兵
        low = 1; high = i - 1;
        while (low <= high) {    // 折半查找插入位置
            mid = (low + high) / 2;
            if (A[mid] > A[0]) high = mid - 1;
            else low = mid + 1;  // A[mid] <= A[0] → 右半区（保证稳定性）
        }
        for (j = i - 1; j >= high + 1; j--)
            A[j+1] = A[j];       // 统一后移
        A[high+1] = A[0];        // 插入
    }
}

// 折半插入排序（Java版，下标从0开始）
void insertSortBinary(int[] A, int n) {
    for (int i = 1; i < n; i++) {
        int temp = A[i];
        int low = 0, high = i - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (A[mid] > temp) high = mid - 1;
            else low = mid + 1;  // 保证稳定性
        }
        for (int j = i - 1; j >= high + 1; j--)
            A[j + 1] = A[j];
        A[high + 1] = temp;
    }
}

⚠️ 注意：折半查找中，当 A[mid] == A[0] 时，应继续在右半区查找（low = mid + 1），这样才能保证排序的稳定性。

三、希尔排序（缩小增量排序）

思想：将序列按增量 $d$ 分成若干组，对每组进行直接插入排序；逐步减小增量直到 $d=1$。

void ShellSort(ElemType A[], int n) {
    int d, i, j;
    for (d = n/2; d >= 1; d = d/2) {     // 增量变化
        for (i = d + 1; i <= n; i++) {    // 对每个组进行插入排序
            if (A[i] < A[i-d]) {
                A[0] = A[i];              // 暂存（A[0]仅作暂存，不做哨兵）
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
                    A[j+d] = A[j];        // 记录后移
                A[j+d] = A[0];
            }
        }
    }
}

// 希尔排序（Java版，下标从0开始）
void shellSort(int[] A, int n) {
    for (int d = n / 2; d >= 1; d /= 2) {
        for (int i = d; i < n; i++) {
            if (A[i] < A[i - d]) {
                int temp = A[i];
                int j;
                for (j = i - d; j >= 0 && temp < A[j]; j -= d)
                    A[j + d] = A[j];
                A[j + d] = temp;
            }
        }
    }
}

⚠️ 增量序列的选择：希尔提出的 $d_1 = n/2, d_{i+1} = \lfloor d_i/2 \rfloor$ 在最坏情况下仍为 $O(n^2)$。Hibbard增量序列 $\{1, 3, 7, 15, \ldots, 2^k-1\}$ 可达 $O(n^{3/2})$。增量序列的最后一个值必须为1。各增量值应互质，否则前面趟次的排序工作可能被"浪费"。

8.3 交换排序

一、冒泡排序

思想：从后往前（或从前往后）两两比较相邻元素，如果逆序就交换。每趟确定一个元素的最终位置。

void BubbleSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = n - 1; j > i; j--) {
            if (A[j-1] > A[j]) {
                swap(A[j-1], A[j]);
                flag = true;
            }
        }
        if (flag == false) return;  // 没有交换，已经有序
    }
}

void bubbleSort(int[] A, int n) {
    for (int i = 0; i < n - 1; i++) {
        boolean flag = false;
        for (int j = n - 1; j > i; j--) {
            if (A[j - 1] > A[j]) {
                int temp = A[j - 1]; A[j - 1] = A[j]; A[j] = temp;
                flag = true;
            }
        }
        if (!flag) return;  // 没有交换，已经有序
    }
}

冒泡排序特征：每趟排序至少确定一个元素的最终位置。

二、快速排序（⭐ 最重要的排序算法）

思想：分治法。选择一个枢轴（pivot），将序列分成两部分——小于枢轴的放左边，大于枢轴的放右边，然后递归处理左右两部分。

void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);   // 排左半部分
        QuickSort(A, pivotpos + 1, high);  // 排右半部分
    }
}

int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low];  // 取第一个元素为枢轴
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];     // 比枢轴小的移到左端
![快速排序Partition过程](图表/DS/DS-17_QuickSortPartition.png)
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];     // 比枢轴大的移到右端
    }
    A[low] = pivot;           // 枢轴元素存放到最终位置
    return low;
}

void quickSort(int[] A, int low, int high) {
    if (low < high) {
        int pivotpos = partition(A, low, high);
        quickSort(A, low, pivotpos - 1);   // 排左半部分
        quickSort(A, pivotpos + 1, high);  // 排右半部分
    }
}

int partition(int[] A, int low, int high) {
    int pivot = A[low];  // 取第一个元素为枢轴
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];     // 比枢轴小的移到左端
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];     // 比枢轴大的移到右端
    }
    A[low] = pivot;           // 枢轴元素存放到最终位置
    return low;
}

🗣️ 大白话：快速排序像分苹果——先选一个标准苹果（枢轴），比它小的放左边筐，比它大的放右边筐，然后对两个筐分别重复这个过程。

⚠️ 快排的关键：枢轴的选择。如果每次都选到最大或最小的元素，效率退化为 $O(n^2)$。

枢轴优化策略：

• 三数取中法（Median-of-Three）：取 A[low]、A[mid]、A[high] 三者的中间值作为枢轴，可以有效避免退化
• 随机选枢轴：在 [low, high] 中随机选取一个元素与 A[low] 交换，再按常规方法划分
• 当子序列很短（如 n ≤ 10）时切换为直接插入排序，减少递归开销

⚠️ 区分概念：一次划分（Partition）确定一个元素的最终位置 ≠ 一趟排序。"一趟排序"指的是对当前递归层的所有子表各进行一次划分。例如第2趟排序可能同时对左右两个子表进行划分，确定2个元素的最终位置。

快速排序的重要特征：

• 每次Partition都能确定一个元素（枢轴）的最终位置
• 快速排序是所有内部排序中平均性能最好的
• 快排的递归栈深度：最好 $O(\log n)$，最坏 $O(n)$
• 快排不产生有序子序列（不像冒泡/选择那样每趟生成全局最值），但每趟排序后枢轴元素一定在最终位置
• 若要判断某序列是否可能是快排某趟后的结果，可检查是否恰好有对应个数的元素已到了最终位置

8.4 选择排序

一、简单选择排序

思想：每趟从待排序元素中选出最小的元素，放到已排序序列的末尾。

void SelectSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min]) min = j;
        if (min != i) swap(A[i], A[min]);
    }
}

void selectSort(int[] A, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min]) min = j;
        if (min != i) {
            int temp = A[i]; A[i] = A[min]; A[min] = temp;
        }
    }
}

二、堆排序（⭐ 重要）

堆的定义：

• 大根堆（最大堆）：$L[i] \geq L[2i]$ 且 $L[i] \geq L[2i+1]$（每个结点 ≥ 其孩子）
• 小根堆（最小堆）：$L[i] \leq L[2i]$ 且 $L[i] \leq L[2i+1]$（每个结点 ≤ 其孩子）

🗣️ 大白话：大根堆就像公司的层级结构——老板（根）的工资最高，每个经理的工资都比手下高。

建堆：从最后一个非叶子结点 $\lfloor n/2 \rfloor$ 开始，自下而上下滤调整。时间复杂度：$O(n)$

💡 建堆 $O(n)$ 的证明：设完全二叉树高度为 $h = \lfloor \log_2 n \rfloor$，第 $i$ 层最多有 $2^{i-1}$ 个结点，每个结点最多下滤 $h-i$ 层。总比较次数 $\leq \sum_{i=1}^{h} 2^{i-1}(h-i)$。令 $j = h-i$，得 $\sum_{j=0}^{h-1} 2^{h-1-j} \cdot j = 2^{h-1} \sum_{j=0}^{h-1} \frac{j}{2^j}$。由差比数列求和知 $\sum_{j=0}^{\infty} \frac{j}{2^j} = 2$，故总次数 $\leq 2^{h-1} \times 2 = 2^h \leq n$，即 $O(n)$。

🗣️ 大白话：建堆之所以是 $O(n)$ 而不是 $O(n \log n)$，是因为大部分结点都在底层、需要调整的层数很少，而少数结点在顶层虽然需要调整很多层但数量极少。

// 大根堆的下滤调整（将以k为根的子树调整为大根堆）
void HeapAdjust(ElemType A[], int k, int len) {
    A[0] = A[k];  // 暂存
    for (int i = 2*k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i+1])
            i++;          // 选较大的孩子
        if (A[0] >= A[i])
            break;        // 已经满足堆性质
        else {
            A[k] = A[i];  // 将孩子上移
            k = i;
        }
    }
    A[k] = A[0];
}

// 大根堆的下滤调整（Java版，下标从1开始）
void heapAdjust(int[] A, int k, int len) {
    int temp = A[k];  // 暂存
    for (int i = 2 * k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i + 1])
            i++;              // 选较大的孩子
        if (temp >= A[i])
            break;            // 已经满足堆性质
        else {
            A[k] = A[i];      // 将孩子上移
            k = i;
        }
    }
    A[k] = temp;
}

堆排序过程（升序用大根堆）：

1. 建立大根堆
2. 将堆顶元素（最大值）与末尾元素交换
3. 对剩余 $n-1$ 个元素重新调整为大根堆
4. 重复2-3

void HeapSort(ElemType A[], int len) {
    // 建堆
    for (int i = len/2; i > 0; i--)
        HeapAdjust(A, i, len);
    // 排序
    for (int i = len; i > 1; i--) {
        swap(A[1], A[i]);        // 堆顶与末尾交换
        HeapAdjust(A, 1, i-1);  // 调整剩余元素
    }
}

void heapSort(int[] A, int len) {
    // 建堆
    for (int i = len / 2; i > 0; i--)
        heapAdjust(A, i, len);
    // 排序
    for (int i = len; i > 1; i--) {
        int temp = A[1]; A[1] = A[i]; A[i] = temp;  // 堆顶与末尾交换
        heapAdjust(A, 1, i - 1);                     // 调整剩余元素
    }
}

堆的插入和删除：

• 插入：将新元素放在末尾，然后上滤调整（Sift Up） $O(\log n)$
• 删除堆顶：将末尾元素替换堆顶，然后下滤调整（Sift Down） $O(\log n)$
• 删除任意位置：将末尾元素替换到删除位置，然后视情况上滤或下滤

// 大根堆的上滤操作（插入新元素后，从末尾向上调整）
void SiftUp(ElemType A[], int k) {
    // k为新元素下标（已放置在末尾）
    A[0] = A[k];           // 暂存
    int i = k / 2;         // 父结点
    while (i > 0 && A[i] < A[0]) {
        A[k] = A[i];       // 父结点下移
        k = i;
        i = k / 2;
    }
    A[k] = A[0];
}

// 大根堆的上滤操作（Java版，下标从1开始）
void siftUp(int[] A, int k) {
    int temp = A[k];
    int i = k / 2;
    while (i > 0 && A[i] < temp) {
        A[k] = A[i];
        k = i;
        i = k / 2;
    }
    A[k] = temp;
}

⚠️ 注意：对堆进行插入/删除操作后，调整的时间复杂度为 $O(\log n)$，而非 $O(n)$。建堆才是 $O(n)$，不要混淆！

💡 堆可以用于：优先队列（任务调度）、Top-K 问题（从海量数据中找前K个最大/最小值）

8.5 归并排序与基数排序

一、归并排序（2路归并）

思想：分治法。将序列分成两半，分别排序，然后将两个有序序列合并成一个有序序列。

void MergeSort(ElemType A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);       // 排左半部分
        MergeSort(A, mid + 1, high);  // 排右半部分
        Merge(A, low, mid, high);      // 合并
    }
}

void mergeSort(int[] A, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(A, low, mid);        // 排左半部分
        mergeSort(A, mid + 1, high);   // 排右半部分
        merge(A, low, mid, high);       // 合并
    }
}

// 合并操作
void merge(int[] A, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (A[i] <= A[j]) temp[k++] = A[i++];
        else temp[k++] = A[j++];
    }
    while (i <= mid)  temp[k++] = A[i++];
    while (j <= high) temp[k++] = A[j++];
    System.arraycopy(temp, 0, A, low, temp.length);
}

合并操作：需要一个辅助数组。

🗣️ 大白话：归并排序就像两队已经排好队的人合并成一队——每次从两队头部各看一个人，较小的先站过来，直到两队都站完。

二、基数排序

思想：不比较关键字大小。把关键字拆成若干"位"（如个位、十位、百位），按位进行分配和收集。

**LSD（最低位优先）**方法：

1. 先按个位分配到0~9号桶，再按顺序收集
2. 再按十位分配和收集
3. 再按百位……直到最高位

**MSD（最高位优先）**方法：先按最高位分组，各组内递归。

LSD示例：对 {278, 109, 063, 930, 589, 184, 505, 269, 008, 083} 排序

时间复杂度：$O(d(n+r))$（$d$ 是位数，$n$ 是元素个数，$r$ 是基数，如十进制 $r=10$）

空间复杂度：$O(r)$（$r$ 个桶/队列）

稳定性：✅ 稳定

⚠️ 基数排序的适用条件：

• 关键字可以方便地拆分成 $d$ 个"组"，且 $d$ 较小
• 每个"组"的取值范围 $r$ 不大
• 关键字之间的比较困难但拆分容易（如字符串、日期）
• 当 $n$ 很大、$d$ 很小、$r$ 较小时效率极高

不适用：关键字取值范围很大、无法拆分为有限位的浮点数等

三、计数排序

思想：统计每个元素出现的次数，然后直接确定每个元素的位置。

三步法：

1. 统计：遍历数组，用辅助数组 C[k] 记录值为 $k$ 的元素个数
2. 累加：$C[i] = C[i] + C[i-1]$，此时 C[k] 表示 $\leq k$ 的元素个数
3. 放置：逆序扫描原数组，将 A[i] 放到 B[C[A[i]]-1] 位置，同时 C[A[i]]--（逆序扫描保证稳定性）

// 计数排序（Java版）
void countingSort(int[] A, int n, int maxVal) {
    int[] C = new int[maxVal + 1];  // 计数数组
    int[] B = new int[n];           // 输出数组
    // 第1步：统计每个值出现次数
    for (int i = 0; i < n; i++) C[A[i]]++;
    // 第2步：累加
    for (int i = 1; i <= maxVal; i++) C[i] += C[i - 1];
    // 第3步：逆序放置（保证稳定性）
    for (int i = n - 1; i >= 0; i--) {
        B[C[A[i]] - 1] = A[i];
        C[A[i]]--;
    }
    System.arraycopy(B, 0, A, 0, n);
}

时间复杂度：$O(n+k)$（$k$ 是数据范围）

空间复杂度：$O(n+k)$（输出数组 + 计数数组）

稳定性：✅ 稳定

⚠️ 适用条件：数据范围 $k$ 不能太大。当 $k > n\log_2 n$ 时，不如基于比较的排序 $O(n\log n)$。适合数据范围有限的非负整数排序。

8.6 内部排序算法总结与比较（⭐ 超级重要！）

各排序算法综合对比表

记忆口诀

不稳定排序："快希选堆"（快速排序、希尔排序、简单选择排序、堆排序）

🗣️ 记忆法：想象一个人"快些选堆"（快点儿选那堆东西），但他比较急躁所以不稳定。

重要结论

1. 没有一种排序在任何情况下都最优
2. 快速排序的平均性能最好（内部排序中）
3. 基于比较的排序算法的时间复杂度下界为 $\Omega(n \log n)$

💡 判定树下界定理（CLRS 定理 8.1）严格证明：

• 任何基于比较的排序算法都可以用一棵**判定树（Decision Tree）**表示：内部结点对应一次 $a_i : a_j$ 的比较，叶结点对应排序结果（排列）
• $n$ 个元素有 $n!$ 种排列，故判定树至少有 $n!$ 个叶结点
• 高度为 $h$ 的二叉树最多有 $2^h$ 个叶结点，因此 $2^h \geq n!$，即 $h \geq \lceil \log_2(n!) \rceil$
• 由 Stirling 公式 $n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$，得 $\log_2(n!) = \Theta(n \log_2 n)$
• 因此最坏情况下比较次数的下界为 $\Omega(n \log n)$

推论：归并排序和堆排序已达到此下界，是渐近最优的基于比较的排序算法。

突破下界：计数排序、基数排序、桶排序等非比较排序可以绕开判定树下界，达到 $O(n)$，但需要对输入数据有额外约束（如数据范围有限）。

4. 堆排序和归并排序在最坏情况下仍为 $O(n \log n)$，但常数因子不同
5. 当序列基本有序时，直接插入排序最快 $O(n)$；而此时快速排序最慢 $O(n^2)$
6. 当 $n$ 较小时，直接插入排序或简单选择排序效率高
7. 稳定排序：直接插入、冒泡、归并、基数、计数
8. 每趟排序能确定一个元素最终位置的：选择排序、快速排序、冒泡排序、堆排序
9. 排序趟数与初始序列有关的：冒泡排序（可提前终止）、快速排序（递归树结构依赖划分）
10. 排序趟数与初始序列无关的：直接插入排序（始终 $n-1$ 趟）、简单选择排序（始终 $n-1$ 趟）、归并排序（始终 $\lceil \log_2 n \rceil$ 趟）、基数排序（始终 $d$ 趟）
11. 比较次数与初始序列无关的：简单选择排序（始终 $n(n-1)/2$ 次）、折半插入排序（仅比较次数无关）、归并排序、基数排序
12. 关键字比较次数和移动次数都与初始序列无关的：基数排序、归并排序、简单选择排序（比较次数无关，移动次数有关）
13. 不适用于链表存储的排序算法：希尔排序（需要按增量随机访问）、堆排序（需要按下标访问父/子结点）、折半插入排序（需要随机访问中间元素）。直接插入排序、冒泡排序、归并排序、基数排序均可用于链表。
14. 排序算法选择决策：
    • $n$ 较小（$\leq 50$）：直接插入排序或简单选择排序
    • $n$ 较大且要求稳定：归并排序
    • $n$ 较大且不要求稳定：快速排序（平均最优）或堆排序（最坏稳定 $O(n\log n)$）
    • 基本有序的序列：直接插入排序（$O(n)$，避免快排退化）
    • 数据范围有限的整数：计数排序或基数排序（$O(n)$ 级别）

算法设计范式总结（⭐ 贯穿全书的思想框架）

💡 408 数据结构中的所有算法，都可以归入以下几大设计范式。掌握范式后，遇到新问题能快速确定解题方向。

⚠️ 考试中的"设计一个高效算法"：

• 题目要求 $O(n)$ → 考虑一趟扫描（双指针/三指针/打标记法/Boyer-Moore投票）
• 题目要求 $O(n\log n)$ → 考虑分治或排序后处理
• 题目要求 $O(\log n)$ → 考虑折半查找/平衡树操作
• 题目有"最优/最小/最大" → 考虑贪心或DP
• 题目涉及"连通/可达/路径" → 考虑BFS/DFS/最短路径

根据排序结果判断排序算法（高频选择题技巧）

⚠️ 2010年真题考法：给出初始序列和前几趟排序结果，判断使用的排序方法。

判断技巧：

例（2010真题）：对 (2, 12, 16, 88, 5, 10)：

• 第1趟：2, 12, 16, 5, 10, 88 → 仅88移到末尾 ✓冒泡
• 验证排除：若希尔排序则 (12, 88, 10) 应变为 (10, 12, 88)，不符；若归并则长度2子段应有序，不符。
• 答案：冒泡排序

折半插入排序 vs 直接插入排序的区别（2012年真题）：

• 排序趟数相同（都是 $n-1$）
• 移动次数相同（取决于初始序列）
• 比较次数不同！折半插入与序列初态无关 $O(n\log n)$，直接插入与序列初态有关 $O(n) \sim O(n^2)$
• 辅助空间都是 $O(1)$

8.7 外部排序

一、外部排序的基本概念

问题：数据量太大，无法全部装入内存，需要借助外存（磁盘）进行排序。

基本方法：归并排序的思想

1. 把文件分成若干段，每段读入内存排序（生成初始归并段/顺串）
2. 对初始归并段进行多趟归并，直到整个文件有序

外部排序时间 = 读写外存时间（主要矛盾！）+ 内部排序时间 + 内部归并时间

🗣️ 大白话：外存（磁盘）读写速度比内存慢几个数量级，所以外部排序的核心优化目标就是减少磁盘I/O次数。

详细分析示例：设文件有2000个记录，内存工作区可容纳500个记录。

• 第一步：分4段，每段500个记录 → 生成4个初始归并段（$r=4$）
• 第二步：2路归并 → 归并趟数 $S = \lceil \log_2 4 \rceil = 2$ 趟

每个记录占1个磁盘块，初始4个归并段分布在两个磁盘上：

若改用4路归并：$S = \lceil \log_4 4 \rceil = 1$ 趟，总I/O = 4000 + 4000 = 8000，显著减少！

性能瓶颈：磁盘I/O次数（读/写磁盘的时间远大于内存中排序的时间）

减少I/O次数的关键：减少归并趟数

$归并趟数 S = \lceil \log_k m \rceil$

其中 $k$ 为归并路数，$m$ 为初始归并段个数。

提高效率的两个方向：

1. 增大归并路数 $k$ → 多路归并（但 $k$ 增大会导致每次选最小元素的比较次数增加 → 用败者树优化）
2. 减少初始归并段个数 $m$ → 使初始归并段更长（用置换-选择排序实现）

二、多路归并与败者树

问题：$k$ 路归并时，每次从 $k$ 个段中选出最小元素需要比较 $k-1$ 次。增大 $k$ 虽然减少趟数，但增加了每趟的比较次数，总比较次数可能不降反升。

败者树（Loser Tree）：一种特殊的完全二叉树，可以将每次选最小值的比较次数从 $k-1$ 降低到 $\lceil \log_2 k \rceil$。

败者树的结构：

• $k$ 个叶结点：存放 $k$ 个归并段的当前元素
• $k-1$ 个内部结点：记录"比赛的失败者"（较大的元素）
• 额外根结点 $ls[0]$：记录"冠军"（最小元素所在归并段编号）

工作原理：

1. 初始化：$k$ 个叶结点两两比较，败者留在父结点，胜者继续向上比较
2. 每次取出最小元素后，从该元素所在归并段读入下一个元素到对应叶结点
3. 仅需沿该叶结点到根的路径重新比较，路径长度 $= \lceil \log_2 k \rceil$

🗣️ 大白话：败者树就像淘汰赛——每次比赛的失败者被记录在结点中，胜利者继续向上比赛。最终冠军就是最小元素。当冠军的归并段送来新选手时，只需沿着"往届对手"重新比赛即可确定新冠军。

败者树的关键性能：

• 构建败者树：$O(k)$ 次比较
• 此后每选一个最小元素：仅需 $\lceil \log_2 k \rceil$ 次比较
• $n$ 个元素、$k$ 路归并的总比较次数：$O(n \log_2 k)$，与 $k$ 无关的量级！
• 每趟归并比较次数：$(n-1) \times \lceil \log_2 k \rceil$（$n$ 个元素选出 $n$ 个最小值，第一个用 $O(k)$ 次建树，此后每次 $\lceil \log_2 k \rceil$ 次）
• 因此增大 $k$ 不会增加总比较次数，只会减少归并趟数

⚠️ 注意：$k$ 也不能无限增大。$k$ 路归并需要 $k$ 个输入缓冲区，受内存限制。实际中常取 $k = 4 \sim 16$。

三、置换-选择排序（生成更长的初始归并段）

问题：内存工作区大小为 $w$，传统方法生成的初始归并段长度也是 $w$。

置换-选择排序可以生成比工作区更长的初始归并段（平均长度为 $2w$）。

算法步骤（设工作区WA容量为 $w$）：

1. 从文件读入 $w$ 个记录到工作区WA
2. 从WA中选出关键字最小的记录 MINIMAX，输出到当前归并段RUN
3. 若文件不空，从文件读入下一个记录补入WA
4. 从WA中所有关键字 $\geq$ MINIMAX 的记录中，选出最小者作为新的MINIMAX输出
5. 重复3-4，直到WA中没有 $\geq$ MINIMAX 的记录
6. 结束当前归并段，开启新的归并段，转步骤2

详细示例（$w = 3$，输入：{17, 21, 05, 44, 10, 12, 56, 32, 29}）：

最终生成2个归并段（传统方法需要3个），减少了归并趟数！

四、最佳归并树

问题：初始归并段长度不同时，如何安排归并顺序使磁盘I/O次数最少？

解决方案：用哈夫曼树的思想构造最佳归并树——短的归并段放在树的低层（多归并几次），长的放在高层（少归并几次）。

$总I/O次数 = 2 \times WPL$

其中 WPL 为带权路径长度，权值为各归并段的长度（记录数）。

对于 $k$ 路归并，构造 $k$ 叉哈夫曼树：

⚠️ 虚段补充规则（非常重要！）：

对于 $k$ 路归并，设有 $n_0$ 个初始归并段（叶结点）。严格 $k$ 叉树满足 $n_0 = (k-1) \cdot n_{k} + 1$（$n_k$ 为度为 $k$ 的结点数），即 $(n_0 - 1) \% (k-1) = 0$。

若 $(n_0 - 1) \% (k-1) = u \neq 0$，则需补充 $(k-1-u)$ 个长度为0的虚段（不增加I/O，仅占位），使得 $(n_0 + 补充数 - 1) \% (k-1) = 0$。

虚段在哈夫曼树中一定处于最底层（权值为0，最先被选中合并）。

示例：3路归并，8个初始归并段（长度分别为 2, 3, 6, 7, 9, 12, 18, 24）

• $(8-1) \% (3-1) = 7 \% 2 = 1 \neq 0$，需补充 $(3-1-1) = 1$ 个虚段（长度0）
• 9个段构造3叉哈夫曼树：每次选3个最小的合并
  • 第1次：{0, 2, 3} → 合并为5
  • 第2次：{5, 6, 7} → 合并为18'
  • 第3次：{9, 12, 18} → 合并为39
  • 第4次：{18', 24, 39} → 合并为81
• $WPL = 0 \times 3 + 2 \times 3 + 3 \times 3 + 6 \times 2 + 7 \times 2 + 9 \times 2 + 12 \times 2 + 18 \times 2 + 24 \times 2$

💡 最佳归并树 = k叉哈夫曼树。它使得长度短的归并段被多次读写（在深层），长度长的归并段被少次读写（在浅层），从而总I/O次数最少。

📝 真题剖析

【2012年408真题】 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一"趟"。下列排序方法中，每一趟处理都能确保将一个尚未确定最终位置之的元素放到其最终位置上的是（）。

Ⅰ. 简单选择排序   Ⅱ. 希尔排序   Ⅲ. 快速排序   Ⅳ. 堆排序   Ⅴ. 二路归并排序

A. 仅Ⅰ、Ⅲ、Ⅳ   B. 仅Ⅰ、Ⅱ、Ⅲ   C. 仅Ⅱ、Ⅲ、Ⅳ   D. 仅Ⅲ、Ⅳ、Ⅴ

解析：

• 简单选择排序 ✅：每趟选出最小/最大的放到最终位置
• 希尔排序 ❌：每趟只是让序列"基本有序"，不保证任何元素到最终位置
• 快速排序 ✅：每趟确定枢轴的最终位置
• 堆排序 ✅：每趟将堆顶（最大/最小值）放到最终位置
• 二路归并排序 ❌：直到最后一趟合并完成前，元素位置可能还会变化

答案选A。

【2012年408真题·综合题】 设有6个有序表 $A(10)$、$B(35)$、$C(40)$、$D(50)$、$E(60)$、$F(200)$（括号内为元素个数），通过5次两两合并最终合成1个升序表，求最坏情况下比较总次数最少的合并方案。

解题方法：哈夫曼树（最佳归并树）思想

两个长度为 $m$、$n$ 的有序表合并，最坏情况下比较 $m + n - 1$ 次。为使总比较次数最少，每次选最短的两个表合并（贪心思想）：

$\text{总比较次数} = 44 + 84 + 109 + 194 + 394 = \mathbf{825}$

💡 推广：$N$（$N \geq 2$）个不等长升序表的合并策略——借用哈夫曼树构造思想，每次选最短的两个表合并，可获得最坏情况下的最佳合并效率。本题考点横跨了排序（归并）和树（哈夫曼）两大知识板块。

【2021年408应用题】 实现"比较计数排序"并使其稳定。

**比较计数排序（Comparison Counting Sort）**思想：对每个元素，统计序列中比它小的元素个数 $count[i]$，则 $count[i]$ 就是该元素在有序序列中的最终下标。

// 比较计数排序（不稳定版）
void compCountSort(int[] A, int[] B, int n) {
    int[] count = new int[n]; // count[i] = A中比A[i]小的元素个数
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (A[i] < A[j]) count[j]++;
            else count[i]++;            // A[i] >= A[j]
    for (int i = 0; i < n; i++)
        B[count[i]] = A[i];
}

⚠️ 稳定性修复：上述代码中 A[i] >= A[j] 时 count[i]++，等值元素中先出现的被计数更多，导致先出现的反而排在后面 → 不稳定。

修复方法：将 else count[i]++ 改为严格地只在 A[i] > A[j] 时 count[i]++，并对 A[i] == A[j] 时按原始下标顺序决定谁的 count 更大：

java复制

if (A[i] < A[j]) count[j]++;
else if (A[i] > A[j]) count[i]++;
// A[i] == A[j] 时：j > i，不操作 → count[j] 自然较大 → j 排在 i 后面 → 稳定

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

【2023年408应用题】 置换-选择排序：内存工作区大小 $m=4$，输入 $n=19$ 个元素，生成初始归并段。

解题要点：

• 初始读入 $m=4$ 个元素到工作区
• 每次从工作区中选 $\geq$ 当前归并段已输出最大值 的最小元素输出
• 工作区中无满足条件的元素时，结束当前归并段，开始新的归并段
• 该题生成了 3 个初始归并段

💡 置换-选择排序的性质：

• 初始归并段平均长度 = $2m$（$m$ 为工作区大小）
• 初始归并段最小长度 = $m$（输入完全逆序时）
• 初始归并段最大长度 = $n$（输入完全升序时，所有元素构成一个归并段）

【2024年408真题】 大根堆 $\{28, 22, 20, 19, 8, 12, 15, 5\}$，连续删除两次堆顶后的结果？

堆删除步骤（大根堆）：

1. 将堆顶（最大值）与最后一个元素交换
2. 堆的规模减1
3. 从堆顶开始向下调整（siftDown）：与较大的子结点交换，直到满足堆的性质

第1次删除堆顶28：

第2次删除堆顶22：

【2024年408真题】 败者树（Loser Tree）中，"冠军"结点 $ls[0]$ 存储的是什么？

💡 $ls[0]$ 存储的是最小关键字所在归并段的段号（不是关键字值本身！）。败者树中间结点存"失败者"（较大值的段号），而 $ls[0]$ 存"冠军"（最小值的段号）。

【2018年408真题】 根据希尔排序某趟结果判断增量。

方法：比较排序前后的序列，找出哪些位置的元素发生了交换。如果间隔为 $d$ 的位置发生了子序列排序，则该趟的增量就是 $d$。

【2025年408应用题】 数组问题 CalMulMax：给定数组 $a[0..n-1]$，求 $f(i) = a[i] \times \max(a[i+1..n-1])$ 的最大值。

三种解法对比：

最优解法（后缀变量，$O(n)$ 时间 $O(1)$ 空间）：

// CalMulMax：求 a[i] × max(a[i+1..n-1]) 的最大值
int calMulMax(int[] a, int n) {
    int suffMax = a[n - 1]; // 后缀最大值
    int suffMin = a[n - 1]; // 后缀最小值（处理负数×负数情况）
    int ans = Integer.MIN_VALUE;
    for (int i = n - 2; i >= 0; i--) {
        // a[i] > 0 时乘 suffMax 最大；a[i] < 0 时乘 suffMin 可能更大
        int cand1 = a[i] * suffMax;
        int cand2 = a[i] * suffMin;
        ans = Math.max(ans, Math.max(cand1, cand2));
        suffMax = Math.max(suffMax, a[i]);
        suffMin = Math.min(suffMin, a[i]);
    }
    return ans;
}

💡 关键技巧：从右往左扫描，同时维护后缀最大值和最小值。考虑负数乘负数为正的情况，因此需要同时维护 suffMax 和 suffMin。

【排序方法识别——根据中间结果反推排序算法】（高频选择题）：

📌 第八章总结