概述
归并排序是目前最高效的排序算法之一，它兼具稳定和低复杂度的特点，其最坏时间复杂度O(nlogn)，空间复杂度O(n)。
归并排序采用计算机科学的分治思想，因此有两种实现方式：自顶向下和自底向上。
自顶向下
针对分治问题，自顶向下是一张常见且较为简便的方式，它采用递归操作。
因此归并排序的原理也就清楚了，首先将数组拆分为两个，进行递归调用，然后合并排序结果。
这是一种可能的自顶向下C实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| void merge(int arr[], unsigned sta, unsigned mid, unsigned end)
{
int tmp[end - sta];
unsigned i = sta, j = mid, k = 0;
while (i < mid && j < end)
{
tmp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
}
while (i < mid)
{
tmp[k++] = arr[i++];
}
while (j < end)
{
tmp[k++] = arr[j++];
}
for (size_t i = sta; i < end; i++)
{
arr[i] = tmp[i - sta];
}
}
void split_merge(int arr[], unsigned sta, unsigned end)
{
if (end - sta < 2) return;
unsigned mid = (sta + end) / 2;
split_merge(arr, sta, mid);
split_merge(arr, mid, end);
merge(arr, sta, mid, end);
}
void sort(int arr[], unsigned n)
{
split_merge(arr, 0, n);
}
|
自底向上
自底向上与自上而下相反，从单个元素开始进行merge和排序，直至所有元素被merge。
这是一种可能的自底向上C实现，它与自顶向下使用相同的merge函数：
1
2
3
4
5
6
7
8
9
10
11
12
| #define MIN(x, y) (((x) < (y)) ? (x) : (y))
void sort(int arr[], unsigned n)
{
for (size_t i = 1; i < n; i *= 2)
{
for (size_t j = 0; j < n; j += 2 * i)
{
merge(arr, j, MIN(j+i, n), MIN(j+i*2, n));
}
}
}
|
总结
两种方式都可以实现归并排序。
对于自底向上，由于免去递归，在n很大时，可以避免调用栈溢出。