未央的技术岛

归并排序的两种方式

概述

归并排序是目前最高效的排序算法之一,它兼具稳定和低复杂度的特点,其最坏时间复杂度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很大时,可以避免调用栈溢出。