-
歸併排序法
鎖定
歸併排序法(Merge Sort,以下簡稱MS)是分治法思想運用的一個典範。
- 中文名
- 歸併排序法
- 外文名
- Merge Sort
- 解 釋
- 分治法思想運用
- 地 位
- 分治法思想運用的一個典範
歸併排序法步驟
其主要算法操作可以分為以下步驟:
Step 1:將n個元素分成兩個含n/2元素的子序列
Step 2:用MS將兩個子序列遞歸排序(最後可以將整個原序列分解成n個子序列)
Step 3:合併兩個已排序好的序列
易知,MS的關鍵在於Merge過程。對於這一過程的理解,算法導論中給出了一個形象的模型。
即假設桌面上有兩堆已排序好的的牌,且每一堆都正面朝下放置。然後我們分別從兩堆牌中選取頂上的一張牌(選取之後,堆頂端又會露出新的頂牌),選取較小的一張,放入輸出堆,另一張放回。
重複這一步驟,最後直到一堆牌為空。由於兩堆牌都是已排序,所以可知,只要將剩下的那堆牌蓋到輸出堆即完成整個排序過程。
歸併排序法小插曲
算法導論為了簡化偽代碼,在此處用了兩張值為∞的哨兵牌。這樣,除非兩堆都露出哨兵牌,否則所取的兩張牌中必有最小值。這一設想避免了檢查每一個堆是否是空的,但是由於無法在程序中表示哨兵牌(或許可以,只是我不知道罷了),我們只能在實際算法中放棄這一設想。
對於A=<5,2,4,7,1,3,2,6>數組,MS的大致操作流程:
[5] [2] [4] [7] [1] [3] [2] [6] \ / \ / \ / \ / [2 5] [4 7] [1 3] [2 6] \ / \ / [2 4 5 7] [1 2 3 6] \ / [1 2 2 3 4 5 6 7]
在遞歸的合併過程中,我們需要動態的創建一個緩存區,作為上面較小牌的輸出堆。一次合併完畢之後,用緩存區的數據覆蓋原始相應數組的數據。
於是乎,我們可以上面的思路,寫出下面的相應代碼(注意邊界成立的條件)
/* 輸 入: a(int[ ]) - 數組地址 nLeft(int) - 左端下標 nRight(int) - 右端下標 輸 出: - 功 能: 歸併排序 */ void CSort::MergeSort(int a[ ], int nLeft, int nRight) { if (nLeft < nRight) { // 剛開始的時候寫了(nLeft + nRight) >> 1 // 結果導致無限遞歸- -,直接報Stack overflow int nMid = (nLeft + nRight) >> 1; // 遞歸分組 MergeSort(a, nLeft, nMid); MergeSort(a, nMid + 1, nRight); // 合併 Merge(a, nLeft, nMid + 1, nRight); } } /* 輸 入: a(int[ ]) - 數組地址 nLeft(int) - 左段數據數組的首下標 nMid(int) - 右段數據數組的首下標 nRight(int) - 右段數據數組的尾下標 輸 出: - 功 能: 合併兩段數據 */ void CSort::Merge(int a[ ], int nLeft, int nMid, int nRight) { // 設置兩個遊標 int nLVer = nLeft; int nMVer = nMid; int nLen = nRight - nLeft + 1; // 創建緩存區,用以保存排序完整的數據 int* pArr = new int [nLen]; int* pVernier = pArr; // 依次從兩堆數據堆中彈出一個數據 // 將較小者置入緩存區 // 這裏注意下nMid表示的意義,理解下取等號的理由 while (nLVer < nMid && nMVer <= nRight) { if (a[nLVer] <= a[nMVer]) { // 很多人都説這麼寫代碼純粹裝B- - // 我承認可讀性很差,但是方便.... *pVernier++ = a[nLVer++]; } else { *pVernier++ = a[nMVer++]; } } // 找到不為空的數據堆,將其粘貼到緩存區後 // 此時pVernier剛好指向緩存區尾數據向右 // 偏移一個單位的位置 while (nLVer < nMid) { *pVernier++ = a[nLVer++]; } while (nMVer <= nRight) { *pVernier++ = a[nMVer++]; } // 將緩存區數據複製回原數組 for (int i = nLeft, k = 0; i <= nRight;) { a[i++] = pArr[k++]; } // 釋放緩存資源 delete [ ] pArr; }