歸并排序算法實(shí)現(xiàn)

1、歸并排序算法實(shí)現(xiàn)（迭代和遞歸）遞歸實(shí)現(xiàn)歸并排序的原理如下:遞歸分割：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遞歸到達(dá)底部后排序返回: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最終實(shí)現(xiàn)排序:#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;時(shí)間復(fù)雜度：最壞和平均時(shí)間復(fù)雜度均為O(nlogn)空間復(fù)雜度：上面的實(shí)現(xiàn)有些問(wèn)題，如果真如上面實(shí)現(xiàn)，在函數(shù)merge中都要使用輔助函 數(shù)Lm和Rn，那么歸并了 logn層，每層消耗空間O(n)，則實(shí)際消耗O(nlogn),再加上?？臻g 的消耗O(longn),總的消耗為O(nlogn+logn).該算法不符合空間復(fù)雜度為O(n)的要求，所以需要 修改，實(shí)現(xià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;空間復(fù)雜度：使用了輔助數(shù)組extra，消耗輔助空間O(n),加上棧空間的消耗O(logn),總 的空間復(fù)雜度為O(n+logn),如果n無(wú)限大，則空間復(fù)雜度可以簡(jiǎn)化為O(n)。歸并排序的迭代實(shí)現(xià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實(shí)現(xiàn)程序如下:#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