Appearance
归并排序与基数排序
概念
这两个算法放在同一篇，是因为它们代表了排序的另一条路线：
- 归并排序（merge sort）：把两个已经有序的序列合并成一个有序序列，这个操作叫「归并」（merge）。从长度为 1 的序列开始两两归并，逐步得到整表有序。
- 基数排序（radix sort）：不比较关键字的大小，而是按"个位 → 十位 → 百位"逐位分类，用分配（distribute）与收集（collect）两个动作完成排序。
它们的关键共同点是：都不靠"元素之间的交换/移动距离"来提速，归并靠"分治合并"，基数靠"按位分桶"。因此两者的时间都与初始序列无关，且都是稳定排序。
一句话记忆：归并是"先分成单元素，再两两拼回去"；基数是"先按个位排队，再按十位排队，再按百位排队"。前者基于比较，后者不基于比较——这是 408 里唯一一个不靠比较的排序算法。
原理
一、归并排序
1. 核心是「归并」这一个动作
归并两个有序表
归并示例：A = 38 49 65 97 B = 13 76
A: 38 49 65 97 B: 13 76
↑ ↑
13 < 38 → 取 13
A: 38 49 65 97 B: 76
↑ ↑
38 < 76 → 取 38, 49, 65
A: 97 B: 76
↑ ↑
76 < 97 → 取 76，B 空 → 接上 97
结果: 13 38 49 65 76 97每次归并的时间与被归并的元素个数成正比，即
2. 两种实现方式
| 实现 | 做法 | 特点 |
|---|---|---|
| 自顶向下（递归） | 把序列一分为二，各自递归排好，再归并 | 代码简洁，需 O(log n) 递归栈 |
| 自底向上（迭代） | 从 width = 1 起，每趟把相邻的两个长度 width 的有序块归并，width 翻倍 | 无递归，适合链式存储，与 shell 排序的"增量"思路形似 |
递归式：
归并趟数：自底向上每趟把有序块长度翻倍，从 1 到
| n | 7 | 8 | 10 | 16 | 17 |
|---|---|---|---|---|---|
| 趟数 | 3 | 3 | 4 | 4 | 5 |
3. 复杂度与特点
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n log n)，最好/最坏/平均都一样，与初始序列无关 |
| 空间复杂度 | O(n)（需要一个等长的辅助数组存放归并结果） |
| 稳定性 | 稳定（归并时用 <= 判断，左半元素优先） |
为什么稳定：两个有序块归并时，若左块的元素等于右块的元素，用 A[i] <= B[j] 取左块的，左块元素原本就在前面，次序得以保持。
归并排序的两个短板：① 必须 O(n) 辅助空间，是本章唯一非原地排序；② 递归实现有函数调用开销，实测常数比快排大。它的长项是性能稳定可预测——现实中的外部排序核心正是它（见下一篇）。
二、基数排序
1. 两个动作：分配与收集
以 3 位数（个位、十位、百位）为例，最低位优先（LSD，Least Significant Digit first）：
第 1 趟：按【个位】把元素分配到 0~9 号队列
第 2 趟：按【十位】把元素分配到 0~9 号队列（保持上一趟的相对次序）
第 3 趟：按【百位】把元素分配到 0~9 号队列
每一趟的收集都是"从 0 号队列开始，依次把各队列首尾相接"分配（distribute）：扫描当前序列，把每个元素按当前位的值放进对应队列（FIFO，尾插）。 收集（collect）：从 0 号队列到 9 号队列，依次把队列中的元素串起来，形成新序列。
分配 收集
┌───────────────────┐ ┌──────────────────┐
│ 0 → [930] │ 从队列 │ 930, 63, 83, ... │
│ 1 → [] │ ────→ │ （即所有元素按 │
│ 2 → [] │ 0..9 顺序 │ 个位从小到大 │
│ ... │ 拼接 │ 重新排好） │
│ 9 → [589, 269] │ │ │
└───────────────────┘ └──────────────────┘2. 为什么必须「最低位优先」
若从最高位开始（MSD），各桶内部还要再递归排序，且收集顺序会打乱前面已经排好的低位次序。LSD 的正确性依赖"每一趟分配-收集都是稳定的"——这一点是它和"稳定排序"的深层联系：
第
趟按第 位排好序后，此前的低 位仍然有序，因为本趟的分桶没有打乱同桶元素之间的相对次序。
3. 复杂度
设关键字有
| 指标 | 值 |
|---|---|
| 时间复杂度 | |
| 空间复杂度 | |
| 稳定性 | 稳定 |
| 是否基于比较 | 否——全程不比较关键字 |
适用条件：
示例
例 1：二路归并排序逐趟推演
对
49, 38, 65, 97, 76, 13, 27（n = 7）做自底向上的二路归并。
第一步，
49 | 38 | 65 | 97 | 76 | 13 | 27
↓ ↓ ↓ ↓ ↓ ↓
(49,38) (65,97) (76,13) (27)
↓ ↓ ↓ ↓
38 49 65 97 13 76 27结果：38 49 65 97 13 76 27
第二步，
(38 49) (65 97) (13 76) (27)
└──┬───┘ └──┬──┘
↓ ↓ （27 无搭档，原地保留）
38 49 65 97 13 27 76结果：38 49 65 97 13 27 76
第三步，
(38 49 65 97) (13 27 76)
↓ ↓
13 27 38 49 65 76 97结果：13 27 38 49 65 76 97 ✅
趟数 =
例 2：二路归并「一趟」的比较次数
归并
38 49 65 97与13 76，需要多少次关键字比较？
指针依次比较：(38,13)→取 13；(38,76)→取 38；(49,76)→取 49；(65,76)→取 65；(97,76)→取 76，右表空，97 直接接上。
比较 5 次，取走 5 个元素，第 6 个元素 97 是"剩下的直接接上"，不再比较。
通用规律：归并两个长度分别为
例 3：基数排序逐趟推演
对
278, 109, 63, 930, 589, 184, 505, 269, 8, 83做 LSD 基数排序（， ）。
第一步，按个位分配并收集：
| 个位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | 930 | — | — | 63, 83 | 184 | 505 | — | — | 278, 8 | 109, 589, 269 |
收集（各队列内部保持原相对次序）：
930 63 83 184 505 278 8 109 589 269第二步，按十位分配并收集：
| 十位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | 505, 8, 109 | — | — | 930 | — | — | 63, 269 | 278 | 83, 184 | — |
收集（注意同一队列里保持第一步留下的次序：505 在 8 前、8 在 109 前；83 在 184 前）：
505 8 109 930 63 269 278 83 184 589第三步，按百位分配并收集：
| 百位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | 8, 63, 83 | 109, 184 | 269, 278 | — | — | 505, 589 | — | — | — | 930 |
收集：
8 63 83 109 184 269 278 505 589 930 ✅验证：升序完成，且全程没有比较过任何两个关键字的大小——只看了它们的各位数字。
C 语言：归并排序（递归 + 迭代）
#include <stdio.h>
#include <stdlib.h>
int *tmp; /* 全局辅助数组，大小 n */
/* ---------- 归并 a[low..mid] 与 a[mid+1..high]，结果存回 a ---------- */
void merge(int a[], int low, int mid, int high) {
for (int k = low; k <= high; k++) tmp[k] = a[k]; /* 拷一份暂存 */
int i = low, j = mid + 1;
for (int k = low; k <= high; k++) {
if (i > mid) a[k] = tmp[j++]; /* 左块用完 */
else if (j > high) a[k] = tmp[i++]; /* 右块用完 */
else if (tmp[i] <= tmp[j]) a[k] = tmp[i++]; /* <= 保证稳定 */
else a[k] = tmp[j++];
}
}
/* ---------- 自顶向下：递归 ---------- */
void mergeSortRec(int a[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSortRec(a, low, mid); /* 排左半 */
mergeSortRec(a, mid + 1, high); /* 排右半 */
merge(a, low, mid, high); /* 归并 */
}
}
/* ---------- 自底向上：迭代 ---------- */
void mergeSortIt(int a[], int n) {
for (int width = 1; width < n; width *= 2) { /* 有序块长度翻倍 */
for (int low = 0; low < n - width; low += 2 * width) {
int mid = low + width - 1;
int high = (low + 2 * width - 1 < n - 1) ? (low + 2 * width - 1) : (n - 1);
merge(a, low, mid, high);
}
}
}
int main(void) {
int s[7] = {49, 38, 65, 97, 76, 13, 27};
int t[7] = {49, 38, 65, 97, 76, 13, 27};
int n = 7;
tmp = (int *)malloc(sizeof(int) * n);
mergeSortRec(s, 0, n - 1);
mergeSortIt(t, n);
printf("递归: "); for (int i = 0; i < n; i++) printf("%d ", s[i]); printf("\n");
printf("迭代: "); for (int i = 0; i < n; i++) printf("%d ", t[i]); printf("\n");
/* 两者都是：13 27 38 49 65 76 97 */
free(tmp);
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
C 语言：基数排序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define R 10 /* 基数：0~9 */
/* 对非负整数做 LSD 基数排序，n 个元素，最多 d 位 */
void radixSort(int a[], int n, int d) {
int *bucket = (int *)malloc(sizeof(int) * n);
int count[R];
for (int p = 1, w = 1; p <= d; p++, w *= 10) { /* w = 1, 10, 100, ... 对应个/十/百位 */
memset(count, 0, sizeof(count));
for (int i = 0; i < n; i++) count[(a[i] / w) % 10]++; /* 先数每桶有几个 */
for (int r = 1; r < R; r++) count[r] += count[r - 1]; /* 前缀和 → 末位下标 */
for (int i = n - 1; i >= 0; i--) { /* 从后往前放，保证稳定 */
bucket[--count[(a[i] / w) % 10]] = a[i];
}
memcpy(a, bucket, sizeof(int) * n); /* 收集：整体搬回 */
}
free(bucket);
}
int main(void) {
int a[10] = {278, 109, 63, 930, 589, 184, 505, 269, 8, 83};
radixSort(a, 10, 3);
for (int i = 0; i < 10; i++) printf("%d ", a[i]);
printf("\n");
/* 8 63 83 109 184 269 278 505 589 930 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
上面用的是「计数排序式的分配收集」——比照着教科书的 10 个链队列更省内存，也更容易写对。核心仍是"先数每桶个数 → 求前缀和 → 从后往前放"：从后往前放这一步保证了稳定性，是不可省的。
Python 对照
# ---------- 归并排序：自顶向下 ----------
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= 保证稳定
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out += left[i:]
out += right[j:]
return out
# ---------- 归并排序：自底向上（与正文趟数推演一致） ----------
def merge_sort_bu(a):
a = a[:]
n, width = len(a), 1
while width < n:
b = []
for s in range(0, n, 2 * width):
L, R = a[s:s + width], a[s + width:s + 2 * width]
i = j = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: b.append(L[i]); i += 1
else: b.append(R[j]); j += 1
b += L[i:]; b += R[j:]
a = b
width *= 2
return a
src = [49, 38, 65, 97, 76, 13, 27]
print("递归:", merge_sort(src))
print("迭代:", merge_sort_bu(src))
# ---------- 基数排序：用桶列表模拟"分配-收集" ----------
def radix_sort(a, d=3, r=10):
a = a[:]
for p in range(d):
buckets = [[] for _ in range(r)]
for x in a:
buckets[(x // (10 ** p)) % 10].append(x) # 分配（尾插，天然稳定）
a = [x for bk in buckets for x in bk] # 收集（0 号桶先出）
return a
nums = [278, 109, 63, 930, 589, 184, 505, 269, 8, 83]
print("基数:", radix_sort(nums))
# 对照标准库：sorted 底层是稳定的 Timsort（归并 + 插入）
print("sorted:", sorted(nums))
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 八大排序大总结表（几乎每套卷子都会出现）
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定性 | 是否比较排序 |
|---|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 折半插入 | O(n log n)* | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 希尔排序 | — | — | 约 | O(1) | 不稳定 | 是 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 | 是 |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 是 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 是 |
| 基数排序 | O(r) | 稳定 | 否 |
* 折半插入的 O(n log n) 指比较次数，总时间仍是 O(n²)。
2. 五条「唯一性」结论（高频原题）
| 问题 | 答案 |
|---|---|
| 唯一不基于比较的排序 | 基数排序 |
| 最坏也是 O(n log n) 的排序 | 堆排序、归并排序 |
| 空间 O(1) 的 O(n log n) 排序 | 堆排序（唯一） |
| 空间 O(n) 的排序 | 归并排序 |
| 一趟就能确定至少一个元素最终位置 | 冒泡、快速、简单选择、堆排序（插入类 / 归并 / 基数不行） |
3. 稳定性速记
- 稳定：插入、折半插入、冒泡、归并、基数 → 记「插折冒归基」
- 不稳定：希尔、快速、简单选择、堆 → 记「希快选堆」
4. 排序趟数与初始状态的关系
| 关系 | 算法 |
|---|---|
| 趟数与初始状态有关 | 冒泡（可提前退出）、快排（递归深度随划分均匀度变化）、希尔 |
| 趟数与初始状态无关 | 简单选择（固定 n−1 趟）、堆排序（固定 n−1 趟）、直接插入（固定 n−1 趟）、归并（固定 |
5. 易错点
- 归并排序的空间是 O(n)，不是 O(log n)。那个 O(log n) 是递归栈的深度（快排的空间也是栈深），而归并额外需要一个等长数组，两者相加仍是 O(n)。考试问"归并排序的空间复杂度"答 O(n)。
- 归并排序的时间与初始序列无关：无论数据怎么排，都是
- 归并趟数是
- 基数排序必须用 LSD（最低位优先） 一次到底；MSD 需要递归且实现复杂。另外，它要求每一趟的分配-收集是稳定的，否则结果会错。
- 基数排序的
- 基数排序不能处理有负数的整数（除非额外做偏移或分正负两半分别排），考试默认非负整数。
- "基数排序比快排快"需要条件：只有
- 归并排序擅长链式存储：自底向上的迭代版在链表上不需要随机访问，这是它比希尔、堆都更适合链表的地方。
小结
- 归并排序的核心动作是「归并两个有序表」：谁小取谁，
- 归并的时间恒为 O(n log n)、趟数
- 基数排序不比较关键字，按"个位 → 十位 → 百位"逐位分配-收集，时间
- 至此内部排序全部讲完。八种算法的时间/空间/稳定性三角关系，是 408 排序部分最稳定的出题点。
- 下一步跨出内存：当待排的记录多到内存装不下时，排序的瓶颈就从"比较次数"变成了"磁盘 I/O 次数"。
下一篇：外部排序
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。