归并排序算法实现(迭代及递归).doc

归并排序算法实现 （迭代和递归）
\递归实现归并排序的原理如下：
递归分割:
34 23 12 55 66 4 2 99 1 45 77 88 99 5

34 23 12 55 66 4 2
99 1 45 77 88 99 5

34 23 12 55
66 4 2
99 1 45 77
88 99 5

34 23
12 55
66 4
2
99 1
45 77
88 99
5
递归到达底部后排序返回:
23 34
12 55
4 66
2
1 99
45 77
88 99
5

12 23 34 55
2 4 66
1 45 77 99
88 99 5

34 23 12 55 66 4 2
99 1 45 77 88 99 5

1 2 4 5 12 23 34 45 55 66 77 88 99 99
最终实现排序：
#include <stdio.h>
void merge(int *array, int low, int center, int high)
{
if(low >= high) return;
int m = center - low + 1;
int n = high - center;
int L[m], R[n];
for(int i=0; i<m; ++i) L[i] = array[low+i];
for(int i=0; i<n; ++i) R[i] = array[low+i+m];
int i,j,k;
for(i=0,j=0,k=low; i<m && j<n;++k) {
if(L[i] > R[j])
array[k] = R[j++];
else
array[k] = L[i++];
}
while(i<m) array[k++] = L[i++];
while(j<n) array[k++] = R[j++];
}
void m_sort(int *array, int low, int high)
{
int center;
if(low < high) {
center = (low + high)/2;
m_sort(array, low, center);
m_sort(array, center+1, high);
merge(array, low, center, high);
}
}
int main()
{
int array[] = {23, 2, 45, 78, 1, 99, 3};
m_sort(array, 0, 6);
for(int i=0; i<=6; ++i) {
printf("%d\n", array[i]);
}
return 0;
}
时间复杂度：最坏和平均时间复杂度均为O(nlogn)
空间复杂度：上面的实现有些问题，如果真如上面实现，在函数merge中都要使用辅助函数L[m]和R[n]，那么归并了logn层，每层消耗空间O(n)，则实际消耗O(nlogn),再加上栈空间的消耗O(longn),总的消耗为O(nlogn+logn).该算法不符合空间复杂度为O(n)的要求，所以需要修改，实现如下：
#include <stdio.h>
#include <string>
using std::string;
void merge(int *array, int *extra, int low, int center, int high)
{
memcpy(extra+low, array+low, (high-low+1)*sizeof(int));
int i,j,k;
for(i=low,j=(center+1),k=low; i<=center && j<=high;++k) {
if(extra[i] > extra[j])
array[k] = extra[j++];
else
array[k] = extra[i++];
}
while(i<=center) array[k++] = extra[i++];
while(j<=high) array[k++] = extra[j++];
}
void m_sort(int *array, int *extra, int low, int high)
{
int center;
if(low < high) {
center = (low + high)/2;
m_sort(array, extra, low, center);
m_sort(array, extra, center+1, high);
merge(array, extra, low, center, high);
}
}
int main()
{
int array[7] = {23, 2, 45, 78, 1, 99, 3};
int extra[7];
m_sort(array, extra, 0, 6);
for(int i=0; i<=6; ++i) {
printf("%d\n", array[i]);
}
return 0;
}
空间复杂度：使用了辅助数组extra，消耗辅助空间O(n)，加上栈空间的消耗O(logn)，总的空间复杂度为
O(n+logn),如果n无限大，则空间复杂度可以简化为O(n)。
归并排序的迭代实现的原理如下：
34 23
12 55
66 4
2 99
1 45
77 88
99 5

23 34
12 55
66 4
2 99
1 45
77 88
5 99

12 23 34 55
2 4 66 99
1 45 77 88
5 99

2 4 12 23 34 55 66 99
1 5 45 77 77 99

1 2 4 5 12 23 34 45 55 66 77 88 99 99
实现程序如下：
#include <stdio.h>
#include <string>
using std::string;
void merge(int *sort, int *list, int low, int center, int high)
{
int i,j,k;
for(i=low,j=(center+1),k=low; i<=center && j<=high;++k) {
if(list[i] > list[j])
sort[k] = list[j++];
else
sort[k] = list[i++];
}
while(i<=center) sort[k++] = list[i++];
while(j<=high) sort[k++] = list[j++];
}
void merge_pass(int *a, int *b, int length, int n)
{
int i;
for(i=0; i<=n-2*length; i+=2*length) {
int center = (i + i + 2*length - 1)/2;
merge(a, b, i, center, i+2*length-1);
}
if((i+length)<n) {
int center = (i + i + 2*length - 1)/2;
merge(a, b, i, center, n-1);
} else {
while(i<n) {
a[i] = b[i];
++i;
}
}
}
void m_sort(int *array, int n)
{
int extra[n];
int length = 1;
while(length < n) {
merge_pass(extra, array, length, n);
length *= 2;
merge_pass(array, extra, length, n);
length *= 2;
}
}
int main()
{
int data[] = {34, 23, 12, 55, 66, 4, 2, 99, 1, 45, 77, 88, 99, 5};
m_sort(data, 14);
for(int i=0; i<14; ++i) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
时间复杂度为：O(nlogn)
空间复杂度为：这里的空间复杂度仅为所需的辅助空间，不需栈空间，为O(n)。