基本思想
歸并排序是分而治之的算法思想的實(shí)際應(yīng)用翰灾，其排序過程是將待排序序列逐層分解直到最后只有一個(gè)元素稚茅，然后在反向合并。
遞歸版歸并排序
如上圖所示
-
被分解為
萎馅，
虹蒋。
-
，
-
峭竣，
晃虫，此時(shí)各組只有一個(gè)元素不再繼續(xù)分解。
- 合并
滥比。
- 分解
為
做院，
，此時(shí)各組只有一個(gè)元素不再繼續(xù)分解寺滚。
- 合并
.
- 合并 4,6結(jié)果
瘸彤。
- 分解
,
。
- 分解
,
愕宋，此時(shí)各組只有一個(gè)元素不再繼續(xù)分解结榄。
- 合并
。
- 合并
邻寿。
- 合并7,11結(jié)果
排序結(jié)束耗绿。
在整個(gè)排序過程中分解過程較為簡單，就是一分為二沐序，核心在合并過程堕绩，即將兩個(gè)有序序列合并為一個(gè)有序序列。
源碼實(shí)現(xiàn)
遞歸版
static void merge(T arr[], int size) {
merge(arr, 0, size - 1);
}
static void merge(T arr[], int L, int R) {
if (L >= R) {
// 遞歸結(jié)束
return;
}
int M = L + (R - L) / 2;
merge(arr, L, M);
merge(arr, M + 1, R);
merge(arr, L, M, R);
}
static void merge(T arr[], int L, int M, int R) {
T *aux = new T[R - L + 1];
for (int i = L; i <= R; i++) {
aux[i-L] = arr[i];
}
// i 索引歸并后的數(shù)組[L, R]奴紧，j索引aux左半邊數(shù)組[0,M-L],k索引aux
// 右半邊[M-L+1, R-L]
for (int i = L, j=0, k=M-L+1; i <= R; i++) {
if (j > M-L) {
arr[i] = aux[k++];
}
else if (k > R - L) {
arr[i] = aux[j++];
}
else if (aux[j] > aux[k]) {
arr[i] = aux[k++];
}
else {
arr[i] = aux[j++];
}
}
delete[]aux;
}
迭代版
static void merge_bu(T arr[], int size) {
for (int sz = 1; sz < size; sz += sz) {
for (int i = 0; i < size - sz; i+=sz*2) {
merge(arr, i, i + sz - 1, size-1< i + 2 * sz - 1?size-1: i + 2 * sz - 1);
}
}
}
