归并排序算法实现

1、归并排序算法实现（迭代和递归）递归实现归并排序的原理如下:递归分割：34 23 12 55 66 4 2 99 1 45 77 88 99 534 23 12 55 66 4 299 1 45 77 88 99 534 23 12 5566 4 299 1 45 7788 99 534 2312 5566 4299 145 7788 995递归到达底部后排序返回:23 3412 554 6621 9945 7788 99512 23 34 552 4 661 45 77 9988 99 534 23 12 55 66 4 299 1 45 77 88 99 51 2 4 5 12 23 34

2、45 55 66 77 88 99 99最终实现排序:#include void merge(int *array, int low, int center, int high)if(low = high) return;int m = center - low + 1;int n = high - center;int Lm, Rn;for(int i=0; im; +i) Li = arraylow+i;for(int i=0; in; +i) Ri = arraylow+i+m;int i,j,k;for(i=0,j=0,k=low; im & j Rj)arrayk = Rj+;els

3、earrayk = Li+;while(im) arrayk+ = Li+;while(jn) arrayk+ = Rj+;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,

4、0, 6);for(int i=0; i=6; +i) printf(%dn, arrayi);return 0;时间复杂度：最坏和平均时间复杂度均为O(nlogn)空间复杂度：上面的实现有些问题，如果真如上面实现，在函数merge中都要使用辅助函 数Lm和Rn，那么归并了 logn层，每层消耗空间O(n)，则实际消耗O(nlogn),再加上栈空间 的消耗O(longn),总的消耗为O(nlogn+logn).该算法不符合空间复杂度为O(n)的要求，所以需要 修改，实现如下：#include #include using std:string;void merge(int *array, in

5、t *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 extraj)arrayk = extraj+;elsearrayk = extrai+;while(i=center) arrayk+ = extrai+;while(j=high) arrayk+ = extraj+;void m_sort(int *array, int *extra, int lo

6、w, 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 array7 = 23, 2, 45, 78, 1,99, 3;int extra7;m_sort(array, extra, 0, 6);for(int i=0; i=6; +i) printf(%dn”, arrayi);ret

7、urn 0;空间复杂度：使用了辅助数组extra，消耗辅助空间O(n),加上栈空间的消耗O(logn),总 的空间复杂度为O(n+logn),如果n无限大，则空间复杂度可以简化为O(n)。归并排序的迭代实现的原理如下：34 2312 5566 42 991 4577 8899 523 3412 5566 42 991 4577 885 9912 23 34 552 4 66 991 45 77 885 992 4 12 23 34 55 66 991 5 45 77 77 991 2 4 5 12 23 34 45 55 66 77 88 99 99实现程序如下:#include #inclu

8、de 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 listj)sortk = listj+;elsesortk = listi+;while(i=center) sortk+ = listi+;while(j=high) sortk+ = listj+;void merge_pass(int *a, int *b, int length, int n)int i;for(i=

9、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(in) ai = bi;+i;void m_sort(int *array, int n)int extran;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