歸并排序和堆排序_圖文

1、歸并排序(MergeSort和堆排序(HeapSort1 歸并排序（MergeSort）歸并排序最差運(yùn)行時(shí)間是O(nlogn，它是利用遞歸設(shè)計(jì)程序的典型例子。歸并排序的最基礎(chǔ)的操作就是合并兩個(gè)已經(jīng)排好序的序列。假設(shè)我們有一個(gè)沒有排好序的序列，那么首先我們使用分割的辦法將這個(gè)序列分割成一個(gè)一個(gè)已經(jīng)排好序的子序列。然后再利用歸并的方法將一個(gè)個(gè)的子序列合并成排序好的序列。分割和歸并的過程可以看下面的圖例。從上圖可以看出，我們首先把一個(gè)未排序的序列從中間分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一個(gè)一個(gè)的數(shù)據(jù)，再把這些數(shù)據(jù)兩兩歸并到一起，使之有序，不停的歸并，最后成為一個(gè)排好序的序列

2、。如何把兩個(gè)已經(jīng)排序好的子序列歸并成一個(gè)排好序的序列呢？可以參看下面的方法。假設(shè)我們有兩個(gè)已經(jīng)排序好的子序列。序列A：1 23 34 65序列B：2 13 14 87那么可以按照下面的步驟將它們歸并到一個(gè)序列中。（1）首先設(shè)定一個(gè)新的數(shù)列C8。（2）A0和B0比較，A0 = 1，B0 = 2，A0 B0，那么C1 = 2（4）A1和B1比較，A1 = 23，B1 = 13，A1 B1，那么C2 = 13（5）A1和B2比較，A1 = 23，B2 = 14，A1 B2，那么C3 = 14（6）A1和B3比較，A1 = 23，B3 = 87，A1 B3，那么C4 = 23（7）A2和B3比較，A2

3、 = 34，B3 = 87，A2 B3，那么C5 = 34（8）A3和B3比較，A3 = 65，B3 = 87，A3 leftmid=(right+left/2;MSort(temp,left,mid;/分割左邊的序列MSort(temp,mid+1,right;/分割右邊的序列Merge(temp,left,mid+1,right;/歸并序列privatestaticvoidMerge(inttemp,intleft,intmid,intrightinti,left_end,num_elements,tmp_pos;left_end=mid-1;tmp_pos=left;num_elemen

4、ts=right-left+1;while(left=left_end&(mid=rightif(myArrayleft=myArraymid/將左端序列歸并到temp數(shù)組中temptmp_pos=myArrayleft;tmp_pos=tmp_pos+1;left=left+1;else/將右端序列歸并到temp數(shù)組中temptmp_pos=myArraymid;tmp_pos=tmp_pos+1;mid=mid+1;while(left=left_end/拷貝左邊剩余的數(shù)據(jù)到temp數(shù)組中temptmp_pos=myArrayleft;left=left+1;tmp_pos=tmp_pos

5、+1;while(mid=right/拷貝右邊剩余的數(shù)據(jù)到temp數(shù)組中temptmp_pos=myArraymid;mid=mid+1;tmp_pos=tmp_pos+1;for(i=0;i1arraySize-;Exchange(0,arraySize;/將最大值放在數(shù)組的最后DownHeap(0;/將序列從0到n-1看成一個(gè)新的序列，重新建立堆privatestaticvoidBuildHeap(for(intv=arraySize/2-1;v=0;v-DownHeap(v;/利用向下遍歷子節(jié)點(diǎn)建立堆privatestaticvoidDownHeap(intvintw=2*v+1;/節(jié)點(diǎn)

6、w是節(jié)點(diǎn)v的第一個(gè)子節(jié)點(diǎn)while(warraySizeif(w+1myArrayww+;/將子節(jié)點(diǎn)w設(shè)置成節(jié)點(diǎn)v下面值最大的子節(jié)點(diǎn)/節(jié)點(diǎn)v已經(jīng)大于子節(jié)點(diǎn)w，有了堆的性質(zhì)，那么返回if(myArrayv=myArraywreturn;Exchange(v,w;/如果不是，就交換節(jié)點(diǎn)v和節(jié)點(diǎn)w的值v=w;w=2*v+1;/繼續(xù)向下找子節(jié)點(diǎn)/交換數(shù)據(jù)privatestaticvoidExchange(inti,intjintt=myArrayi;myArrayi=myArrayj;myArrayj=t;堆排序主要用于超大規(guī)模的數(shù)據(jù)的排序。因?yàn)樗恍枰~外的存儲(chǔ)空間，也不需要大量的遞歸。3 幾種O(

7、nlogn算法的初步比較我們可以從下表看到幾種O(nlogn算法的效率的區(qū)別。所有的數(shù)據(jù)都使用.Net的Random類產(chǎn)生，每種算法運(yùn)行100次，時(shí)間的單位為毫秒。500隨機(jī)整數(shù)5000隨機(jī)整數(shù)20000隨機(jī)整數(shù)合并排序0.31251.56257.03125Shell排序0.31251.256.875堆排序0.468752.18756.71875快速排序0.156250.6252.8125從上表可以明顯地看出，快速排序是最快的算法。這也就給了我們一個(gè)結(jié)論，對(duì)于一般的應(yīng)用來(lái)說(shuō)，我們總是選擇快速排序作為我們的排序算法，當(dāng)數(shù)據(jù)量非常大（百萬(wàn)數(shù)量級(jí)）我們可以使用堆排序，如果內(nèi)存空間非常緊張，我們可以使用Shell排序。但是這意味著我們不得不損失速度。 /*【Author】：flyingbread*【Date】：2007