歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(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中,一次合并排序就完成了。
核心代碼
<a></a>
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++;
}
}
// 若第一段序列還沒掃描完,将其全部複制到合并序列
while (i <= mid) {
array2[k] = array[i];
i++;
k++;
// 若第二段序列還沒掃描完,将其全部複制到合并序列
while (j <= high) {
array2[k] = array[j];
j++;
// 将合并序列複制到原始序列中
for (k = 0, i = low; i <= high; i++, k++) {
array[i] = array2[k];
}
掌握了合并的方法,接下來,讓我們來了解 如何分解。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL1QjN4cDNzgzMtgTO4AzMzUDMxIjM0AjNxAjMtczM4gTMz8CX0AjNxAjMvw1NzgDOxMzLcd2bsJ2Lc12bj5ycn9Gbi52YuUTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
在某趟歸并中,設各子表的長度為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(n)
穩定
較複雜
歸并排序的形式就是一棵二叉樹,它需要周遊的次數就是二叉樹的深度,而根據完全二叉樹的可以得出它的時間複雜度是O(n*log2n)。
由前面的算法說明可知,算法處理過程中,需要一個大小為n的臨時存儲空間用以儲存合并序列。
在歸并排序中,相等的元素的順序不會改變,是以它是穩定的算法。
若從空間複雜度來考慮:首選堆排序,其次是快速排序,最後是歸并排序。
若從穩定性來考慮,應選取歸并排序,因為堆排序和快速排序都是不穩定的。
若從平均情況下的排序速度考慮,應該選擇快速排序。
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
本文轉自靜默虛空部落格園部落格,原文連結:http://www.cnblogs.com/jingmoxukong/p/4308823.html,如需轉載請自行聯系原作者