所有人都可以看懂的算法-遞歸與分治算法

很多經典算法都使用了分治法的思想，如：

• 二分搜索法（Binary Search）
• 歸併排序（Merge Sort）
• 快速排序（Quicksort ）
• 漢諾塔問題（Hanoi）
• Strassen算法（Strassen’s Algorithm）

下面我們以歸併排序來說明。

public static int[] mergeSort(int[] arr, int low, int high) {

int mid = (low + high) / 2;

if (low < high) {

mergeSort(arr, low, mid);

mergeSort(arr, mid + 1, high);

merge(arr, low, mid, high);

}

return arr;

}

private static void merge(int[] arr, int low, int mid, int high) {

int[] temp = new int[high - low + 1];

int i = low;// 左指針

int j = mid + 1;// 右指針

int k = 0;

// 把較小的數先移到新數組中

while (i <= mid && j <= high) {

if (arr[i] < arr[j]) {

temp[k++] = arr[i++];

} else {

temp[k++] = arr[j++];

}

}

// 把左邊剩餘的數移入數組

while (i <= mid) {

temp[k++] = arr[i++];

}

// 把右邊邊剩餘的數移入數組

while (j <= high) {

temp[k++] = arr[j++];

}

// 把新數組中的數覆蓋nums數組

for (int k2 = 0; k2 < temp.length; k2++) {

arr[k2 + low] = temp[k2];

}

}

例子中將待排序的數組每次一分為二，然後遞歸分割直到不能分割為止（把單個元素當做一個有序數組），merge方法將兩個有序序列合併為一個有序序列。採用雙指針遍歷兩個有序數組。即左指針（i）指向每次分割後左邊數組第一個元素，右指針（j）指向每次分割後右邊數組第一個元素。然後依次從小到大填充到temp數組中。

下面用兩張圖來加深理解

根據分治思想結合歸併排序例子我們可以總結下采用分治法要解決的問題需要具備的特徵有

1. 問題可分解為若干規模較小的相同類型的子問題。
2. 子問題規模縮小到一定程度後很容易的求解。
3. 利用子問題的解可求解原問題的解。
4. 各個子問題是相互獨立的，子問題直接不包含公共的子問題。

---

分享到:

---

閱讀更多 程序員列儂 的文章

關鍵字: 遞歸 算法 問題

---