歸并排序是利用遞歸和分而治之的技術(shù)將數(shù)據(jù)序列劃分成為越來(lái)越小的半子表,再對(duì)半子表排序,最后再用遞歸步驟將排好序的半子表合并成為越來(lái)越大的有序序列,歸并排序包括兩個(gè)步驟,分別為:
1)劃分子表
2)合并半子表
首先我們來(lái)討論歸并算法,歸并算法將一系列數(shù)據(jù)放到一個(gè)向量中,索引范圍為[first,last],這個(gè)序列由兩個(gè)排好序的子表構(gòu)成,以索引終點(diǎn)(mid)為分界線,以下面一個(gè)序列為例
7,10,19,25,12,17,21,30,48
這樣的一個(gè)序列中,分為兩個(gè)子序列 7,10,19,25 和 12,17,21,30,48,如下圖所示:
再使用歸并算法的時(shí)候的步驟如下:
第一步:比較v[indexA]=7和v[indexB]=12,將較小的v[indexA]取出來(lái)放到臨時(shí)向量tempArray中,然后indexA加1
第二步:比較v[indexA]=10和v[indexB]=12,將較小的10放到臨時(shí)變量tempArray中,然后indexA++;
第三步:比較v[indexA]=19與v[indexB]=12,將較小的12存放到臨時(shí)變量tempArray中,然后indexB++;
第四步到第七步:按照以上規(guī)則,進(jìn)行比對(duì)和存儲(chǔ),得到如下結(jié)果:
最后一步:將子表b中剩余項(xiàng)添加到臨時(shí)向量tempArray中
然后將臨時(shí)變量中的值按照索引位置,拷貝回向量v中,就完成了對(duì)向量v的歸并排序
算法函數(shù)為:
1 public void Merger(int[] v, int first, int mid, int last)
2 {
3 Queue<int> tempV = new Queue<int>();
4 int indexA, indexB;
5 //設(shè)置indexA,并掃描subArray1 [first,mid]
6 //設(shè)置indexB,并掃描subArray2 [mid,last]
7 indexA = first;
8 indexB = mid;
9 //在沒(méi)有比較完兩個(gè)子標(biāo)的情況下,比較 v[indexA]和v[indexB]
10 //將其中小的放到臨時(shí)變量tempV中
11 while (indexA < mid && indexB < last)
12 {
13 if (v[indexA] < v[indexB])
14 {
15 tempV.Enqueue(v[indexA]);
16 indexA++;
17 }
18 else
19 {
20 tempV.Enqueue(v[indexB]);
21 indexB++;
22 }
23 }
24 //復(fù)制沒(méi)有比較完子表中的元素
25 while (indexA < mid)
26 {
27 tempV.Enqueue(v[indexA]);
28 indexA++;
29 }
30 while (indexB < last)
31 {
32 tempV.Enqueue(v[indexB]);
33 indexB++;
34 }
35 int index = 0;
36 while (tempV.Count > 0)
37 {
38 v[first+index] = tempV.Dequeue();
39 index++;
40 }
41 }
實(shí)現(xiàn)歸并排序;歸并排序算法分為兩步,第一步:先將原來(lái)的數(shù)據(jù)表分成排好序的子表,然后調(diào)用 Merger 對(duì)子表進(jìn)行歸并,使之成為有序表,例如有如下向量:
25,10,7,19,3,48,12,17,56,30,21
對(duì)此序列進(jìn)行歸并排序的步驟為:

歸并算法函數(shù)為
1 public void MergerSort(int[] v, int first, int last)
2 {
3 if (first + 1 < last)
4 {
5 int mid = (first + last) / 2;
6 MergerSort(v, first, mid);
7 MergerSort(v, mid, last);
8 Merger(v, first, mid, last);
9 }
10 }
歸并算法的劃分子表和歸并子表與原數(shù)據(jù)序列次序無(wú)關(guān),因此算法的最壞情況,最壞情況和平均情況時(shí)間復(fù)雜度是一樣的
下面是歸并算法的函數(shù)調(diào)用圖
示例程序: MergerSort.rar