分治法
分治法的思想是：將原問題分解成若干個規(guī)模較小但是與原問題類似的問題剩彬，遞歸地求解這些子問題盛末，然后再合并這些子問題的解來建立原問題的解弹惦。
分治法在每層遞歸時都有三個步驟：
- 分解： 將原問題分解為若干個子問題，這些問題是原問題的規(guī)模較小的實(shí)例
- 解決： 遞歸求解子問題悄但，若子問題規(guī)模足夠小棠隐，則直接求解
- 合并： 合并這些子問題的解成原問題的解。
歸并排序
歸并排序就是采用分治法的思想檐嚣。
-
分解： 分解待排序的
個元素的序列成各具
個元素的兩個子序列助泽。
- 解決： 遞歸排序兩個子序列。
- 合并： 合并兩個已排序的子序列以產(chǎn)生已排序的答案嚎京。
其遞歸思想如下圖所示
3eb110a0a8f74306b4b1d8803568aa5cpng
將數(shù)組分為含有個元素的兩個數(shù)組嗡贺，然后分別遞歸排序，然后再次拆分鞍帝，直到最后只剩一個元素诫睬。然后開始?xì)w并。這個算法的難點(diǎn)在于子序列的合并帕涌，合并思想如下
42f1960cdb5f4366acfcc35c4f9497c9png
首先需要創(chuàng)建一個數(shù)組摄凡，我們記為，數(shù)組的長度為兩個子序列之和蚓曼。從兩個子序列的最左端開始亲澡，誰的元素小（大）就將誰的放入到
中辟躏。
歸并排序代碼實(shí)現(xiàn)
public class MergeSort {
public static int[] sort(int[] arr, int start, int end) {
if (start == end) {
// 如果開始索引和結(jié)束索引相等谷扣，說明只需處理一個元素，所以直接返回此元素即可捎琐。
return new int[] {arr[start]};
} else {
// 這里減一不減一都可以会涎，如果減一是把奇數(shù)元素的子序列放到了最右邊，否則是放到了最左邊來處理
// 等價于(end-start)/2瑞凑，由于位運(yùn)算速度更快末秃，所以這里使用位運(yùn)算。
int half = ((end - start - 1) >> 1);
int[] left = sort(arr, start, start + half);
int[] right = sort(arr, start + half + 1, end);
// 合并子序列
int maxLength = left.length + right.length;
int[] mergeArr = new int[maxLength];
int lIndex = 0;
int rIndex = 0;
for (int i = 0; i < maxLength; i++) {
if (lIndex < left.length && rIndex < right.length) {
if (left[lIndex] <= right[rIndex]) {
mergeArr[i] = left[lIndex];
lIndex++;
} else {
mergeArr[i] = right[rIndex];
rIndex++;
}
} else if (lIndex < left.length) {
mergeArr[i] = left[lIndex];
lIndex++;
} else {
mergeArr[i] = right[rIndex];
rIndex++;
}
}
return mergeArr;
}
}
public static void main(String[] args) {
int[] arr = {2, 5, 1, 8, 9, 7, 6, 12, 4};
int[] sortRes = sort(arr, 0, arr.length - 1);
for (int i : sortRes) {
System.out.printf("%d\t", i);
}
System.out.println();
}
}
時間復(fù)雜度分析
我們先看遞歸深度籽御，從上面的圖中我們能看出遞歸深度應(yīng)該是练慕。有根節(jié)點(diǎn)所以加一惰匙，最后一級如果不是滿樹的狀態(tài)會被忽略掉。
設(shè)铃将，那么遞歸式的和為
（從0開始是為了方便計算）项鬼。此算法中的基本操作就是合并，假設(shè)第一層的時間復(fù)雜度是
次劲阎，第二層每個遞歸就是
绘盟，以此類推，最后得到總的時間復(fù)雜度為：
舍去常數(shù)項(xiàng)和對算法影響較小的項(xiàng)最終就是或者寫為
在算法中
通常表示以2為底
的對數(shù)悯仙。
