归并排序
稳定排序
归并排序 是 CoddyKit 上的免费 C Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。
稳定排序
归并排序是一种分治排序算法：它将数组从中间分成两半，分别对两半排序，然后再将它们合并起来。无论在哪种情况下，它的时间复杂度都是 O(n log n)，并且是稳定的。
划分步骤
递归地在中点处分割数组，直到每个部分只包含一个元素。单个元素显然已经排好序，这就是基本情况。
合并步骤
核心操作是将两个已经排好序的序列合并为一个序列。使用索引指针同时遍历两者，每次复制当前位于前端的较小元素。
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}为什么它是稳定的
合并操作使用 a[i] <= a[j]，因此当两个元素相等时，会先取左侧序列中的元素。由于左侧序列保存的是较早出现的元素，因此可以保持原有顺序。
递归驱动过程
归并排序会分别对两半进行递归，然后合并它们。我们传入一个共享的临时缓冲区，以避免每次调用都分配内存。
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}内存使用
与快速排序不同，归并排序需要使用 O(n) 的额外内存存放合并缓冲区。在内存紧张的情况下处理超大数组时，这是它的主要缺点。
保证为 O(n log n)
递归过程始终将数组对半分割，因此有 log n 层；每一层都会合并 n 个元素。因此，与快速排序不同，归并排序在最佳、平均和最坏情况下的时间复杂度都为 O(n log n)。
计算合并层数
递归层数为 ceil(log2 n)。让我们计算几种规模下的层数。
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}自底向上的归并排序
一种迭代式变体会先合并大小为 1 的序列，再合并大小为 2 的序列，然后是大小为 4 的序列，每轮都将大小翻倍。它完全避免了递归，并且适合链表。
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}何时选择归并排序
在以下情况下，优先选择归并排序：
- 保证为 O(n log n)，不存在糟糕的情况
- 需要稳定性
- 对链表排序（不需要随机访问）
- 对大到无法放入 RAM 的数据进行外部排序
归并排序与快速排序
快速排序在实践中通常更快，并且是原地排序，但它不稳定，而且最坏情况可能很糟。归并排序是稳定的，并且有保证的复杂度上界，但会使用额外内存。请根据您的限制条件进行选择。
快速检查
测试您对归并排序的理解。
回顾
您已经学习了归并排序。
- 将数组对半划分，分别排序，然后合并
- 合并时相等键优先选择左侧元素，因此具有稳定性
- 所有情况下都保证为 O(n log n)
- 需要 O(n) 的额外内存；非常适合链表和外部排序
常见问题解答
「归并排序」课时是免费的吗？
是的 — 「归并排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。
「归并排序」这节课中我会学到什么？
稳定排序 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 C Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「归并排序」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 C Academy 课中编写并运行代码吗？
能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。