目錄
- 要點
- 歸并排序的基本思想
- 算法分析
- 歸并排序算法的性能
- 時間複雜度
- 空間複雜度
- 算法穩定性
- 歸并排序和堆排序、快速排序的比較
- 完整參考代碼
- Java版本
- 參考資料
- 相關閱讀
回到頂部
要點
歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序的基本思想
将待排序序列R[0...n-1]看成是n個長度為1的有序序列，将相鄰的有序表成對歸并，得到n/2個長度為2的有序表；将這些有序序列再次歸并，得到n/4個長度為4的有序序列；如此反複進行下去，最後得到一個長度為n的有序序列。
綜上可知：
歸并排序其實要做兩件事：
（1）“分解”——将序列每次折半劃分。
（2）“合并”——将劃分後的序列段兩兩合并後排序。
我們先來考慮第二步，如何合并？
在每次合并過程中，都是對兩個有序的序列段進行合并，然後排序。
這兩個有序序列段分别為 R[low, mid] 和 R[mid+1, high]。
先将他們合并到一個局部的暫存數組R2中，帶合并完成後再将R2複制回R中。
為了友善描述，我們稱 R[low, mid] 第一段，R[mid+1, high] 為第二段。
每次從兩個段中取出一個記錄進行關鍵字的比較，将較小者放入R2中。最後将各段中餘下的部分直接複制到R2中。
經過這樣的過程，R2已經是一個有序的序列，再将其複制回R中，一次合并排序就完成了。
核心代碼
public void Merge( int[] array, int low, int mid, int high) {
int i = low; // i是第一段序列的下标
int j = mid + 1; // j是第二段序列的下标
int k = 0; // k是臨時存放合并序列的下标
int[] array2 = new int[high - low + 1]; // array2是臨時合并序列
// 掃描第一段和第二段序列，直到有一個掃描結束
while (i <= mid && j <= high) {
// 判斷第一段和第二段取出的數哪個更小，将其存入合并序列，并繼續向下掃描
if (array[i] <= array[j]) {
array2[k] = array[i];
i++;
k++;
} else {
array2[k] = array[j];
j++;
k++;
}
}
// 若第一段序列還沒掃描完，将其全部複制到合并序列
while (i <= mid) {
array2[k] = array[i];
i++;
k++;
}
// 若第二段序列還沒掃描完，将其全部複制到合并序列
while (j <= high) {
array2[k] = array[j];
j++;
k++;
}
// 将合并序列複制到原始序列中
for (k = 0, i = low; i <= high; i++, k++) {
array[i] = array2[k];
}
}
掌握了合并的方法，接下來，讓我們來了解 如何分解。
在某趟歸并中，設各子表的長度為gap，則歸并前R[0...n-1]中共有n/gap個有序的子表：R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。
調用Merge将相鄰的子表歸并時，必須對表的特殊情況進行特殊處理。
若子表個數為奇數，則最後一個子表無須和其他子表歸并（即本趟處理輪空）：若子表個數為偶數，則要注意到最後一對子表中後一個子表區間的上限為n-1。
核心代碼
public void MergePass( int[] array, int gap, int length) {
int i = 0;
// 歸并gap長度的兩個相鄰子表
for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
Merge(array, i, i + gap - 1, i + 2 * gap - 1);
}
// 餘下兩個子表，後者長度小于gap
if (i + gap - 1 < length) {
Merge(array, i, i + gap - 1, length - 1);
}
}
public int[] sort( int[] list) {
for ( int gap = 1; gap < list.length; gap = 2 * gap) {
MergePass(list, gap, list.length);
System.out.print("gap = " + gap + ":\t");
this.printAll(list);
}
return list;
}
回到頂部
算法分析
歸并排序算法的性能
| 排序類别 | 排序方法 | 時間複雜度 | 空間複雜度 | 穩定性 | 複雜性 | ||
| 平均情況 | 最壞情況 | 最好情況 | |||||
| 歸并排序 | 歸并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 穩定 | 較複雜 |
時間複雜度
歸并排序的形式就是一棵二叉樹，它需要周遊的次數就是二叉樹的深度，而根據完全二叉樹的可以得出它的時間複雜度是O(n*log2n)。
空間複雜度
由前面的算法說明可知，算法處理過程中，需要一個大小為n的臨時存儲空間用以儲存合并序列。
算法穩定性
在歸并排序中，相等的元素的順序不會改變，是以它是穩定的算法。
歸并排序和堆排序、快速排序的比較
若從空間複雜度來考慮：首選堆排序，其次是快速排序，最後是歸并排序。
若從穩定性來考慮，應選取歸并排序，因為堆排序和快速排序都是不穩定的。
若從平均情況下的排序速度考慮，應該選擇快速排序。
回到頂部
完整參考代碼
Java版本
View Code
運作結果
排序前: 9 1 5 3 4 2 6 8 7
gap = 1: 1 9 3 5 2 4 6 8 7
gap = 2: 1 3 5 9 2 4 6 8 7
gap = 4: 1 2 3 4 5 6 8 9 7
gap = 8: 1 2 3 4 5 6 7 8 9
排序後: 1 2 3 4 5 6 7 8 9
回到頂部
參考資料
《資料結構習題與解析》（B級第3版）
轉自：http://www.cnblogs.com/jingmoxukong/p/4308823.html
【最後一步還一個遞歸的方法】http://www.cnblogs.com/jillzhang/archive/2007/09/16/894936.html