Like Share Discussion Bookmark Smile

J.J. Huang   2020-03-14   排序演算法   瀏覽次數:

排序演算法 | 合併排序

合併排序(英語:Merge sort,或mergesort),是建立在合併操作上的一種有效的排序演算法,效率為O(n log n)(大O符號)。1945年由約翰·馮·紐曼首次提出。該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用,且各層分治遞迴可以同時進行。

使用合併排序為一列數字進行排序的過程:

採用分治法:

  • 分割:遞迴地把目前序列平均分割成兩半。
  • 整合:在保持元素順序的同時將上一步得到的子序列整合到一起(合併)。

合併操作(merge),也叫合併演算法,指的是將兩個已經排序的序列合併成一個序列的操作。合併排序演算法依賴合併操作。

  • 遞迴法(Top-down)
    1.申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合併後的序列
    2.設定兩個指標,最初位置分別為兩個已經排序序列的起始位置
    3.比較兩個指標所指向的元素,選擇相對小的元素放入到合併空間,並移動指標到下一位置
    4.重複步驟3直到某一指標到達序列尾
    5.將另一序列剩下的所有元素直接複製到合併序列尾

  • 疊代法(Bottom-up)
    原理如下(假設序列共有n個元素):

    1.將序列每相鄰兩個數字進行合併操作,形成ceil(n/2)個序列,排序後每個序列包含兩/一個元素
    2.若此時序列數不是1個則將上述序列再次合併,形成ceil(n/4)個序列,每個序列包含四/三個元素
    3.重複步驟2,直到所有元素排序完畢,即序列數為1

範例說明

假設現在有一個待排序的序列,[5,2,4,7,1,3,2,2],那麼我們就需要將該序列進行分治,先將其分成兩份:[5,2, 4,7]和[1,3,2,2],再將這兩份分別分成兩份:[5,2]和[4,7];[1,3]和[2,2],最後將這四部分再次分別分為兩份,最後就將整個序列分為了八份。需要注意的是,在分的過程中,不需要遵循任何規則,關鍵在於合併,合併的過程中便實現了元素的排序。

實作範例(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
// 分解
if (left < right) {
int mid = (left + right) / 2; // 中間索引
// 向左遞歸進行分解
mergeSort(arr, left, mid, temp);
// 向右遞歸進行分解
mergeSort(arr, mid + 1, right, temp); // mid + 1,中間位置的後一個位置才是右邊序列的開始位置
// 每分解一輪便合併一輪
merge(arr, left, right, mid, temp);
}
}

/**
* 合併的方法
*
* @param arr 待排序的數組
* @param left 左邊有序序列的初始索引
* @param right 中間索引
* @param mid 右邊有序序列的初始索引
* @param temp 做中轉的數組
*/
public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
int i = left; // 初始化i,左邊有序序列的初始索引
int j = mid + 1; // 初始化j,右邊有序序列的初始索引(右邊有序序列的初始位置即為中間位置的後一個位置)
int t = 0; // 指向temp數組的當前索引,初始為0
// 先把左右兩邊的數據(已經有序)按規則填充到temp數組
// 直到左右兩邊的有序序列,有一邊處理完成為止
while (i <= mid && j <= right) {
// 如果左邊有序序列的當前元素小於或等於右邊有序序列的當前元素,就將左邊的元素填充到temp數組中
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++; // 索引後移
i++; // i後移
} else {
// 反之,將右邊有序序列的當前元素填充到temp數組中
temp[t] = arr[j];
t++; // 索引後移
j++; // j後移
}
}
// 把有剩餘數據的一邊的元素填充到temp中
while (i <= mid) {
// 此時說明左邊序列還有剩餘元素
// 全部填充到temp數組
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
// 此時說明左邊序列還有剩餘元素
// 全部填充到temp數組
temp[t] = arr[j];
t++;
j++;
}
// 將temp數組的元素複製到原數組
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}


public static void main(String[] args) {
int[] arr = {
3,
44,
38,
5,
47,
15,
36,
26,
27,
2,
46,
4,
19,
50,
48
};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}

結果:

1
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

對於該排序算法,有兩個部分組成,分解和合併。

首先講分解,在前面也說到了,我們需要將待排序的序列不停地進行分解,通過兩個索引變量控制,一個初始索引,一個結尾索引。只有當兩索引重合才結束分解。此時序列被分解成了十五個小份,這樣分解工作就完成了。

接下來是合併,合併操作也是最麻煩的,也是通過兩個索引變量i,j。開始i在左邊序列的第一個位置,j在右邊序列的第一個位置,然後就是尋找左右兩個序列中的最小值,放到新序列中,這時可能會出現一邊的元素都放置完畢了,而另外一邊還存在元素,此時只需將剩餘的元素按順序放進新序列即可,因為這時左右兩邊的序列已經是有序的了,最後將新序列複製到舊序列。這裡也特別需要注意,因為合併的過程是分步的,而並非一次合併完成,所以數組的索引是在不斷變化的。


註:以上參考了
維基百科-合併排序
演算法筆記
程式员必须掌握的核心算法有哪些?
程式员那些必须掌握的排序算法(上)
程式员那些必须掌握的排序算法(下)