概述
归并排序是目前最高效的排序算法之一,它兼具稳定和低复杂度的特点,其最坏时间复杂度O(nlogn)
,空间复杂度O(n)
。
归并排序采用计算机科学的分治思想,因此有两种实现方式:自顶向下和自底向上。
自顶向下
针对分治问题,自顶向下是一张常见且较为简便的方式,它采用递归操作。
因此归并排序的原理也就清楚了,首先将数组拆分为两个,进行递归调用,然后合并排序结果。
这是一种可能的自顶向下C实现:
cvoid 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函数:
c#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很大时,可以避免调用栈溢出。
评论
发表评论