原創(chuàng)-轉(zhuǎn)載請(qǐng)注明出處。
分治法
分治法是一種很重要的算法，也就是“分而治之”的意思，就是把一個(gè)復(fù)雜的問題分解成兩個(gè)或者多個(gè)相似的子問題，直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。
比如二分搜索算法，排序算法中的快速排序和歸并排序都屬于分治法的一種。下面我們來(lái)看看歸并排序和快速排序算法的實(shí)現(xiàn)。
歸并排序
簡(jiǎn)介
歸并排序（Merge sort）,是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為O(n log n)。最優(yōu)時(shí)間復(fù)雜度，O(n),平均時(shí)間復(fù)雜度為O(n log n)。由上圖我們可以了解到歸并排序的過程。
實(shí)例分析
以數(shù)組6 5 3 1 8 7 2 4為例。首先遞歸的將數(shù)組一分為2，并對(duì)子數(shù)組排序
[6, 5, 3, 1] [8, 7, 2, 4]
[6, 5] [3, 1] [8, 7] [2, 4]
[6], [5] [4], [3] [7], [8] [2], [4]
然后向上回溯，將兩個(gè)數(shù)組合并成有序數(shù)組
[6], [5] [4], [3] [7], [8] [2], [4]
[5, 6] [3, 4] [7, 8] [2, 4]
[3, 4, 5, 6] [2, 4, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
動(dòng)圖如下所示
兩個(gè)有序數(shù)組排序
/**
*
* @param a 有序數(shù)組a
* @param b 有序數(shù)組b
* @param result 結(jié)果數(shù)組
*/
public static void merge2(int[] a,int [] b, int[] result){
int i = 0 , j = 0 , k = 0 ;
while (i < a.length && j < b.length){
if (a[i] < b[j]){
result[k++] = a[i++];
}else {
result[k++] = b[j++];
}
}
while (i < a.length){
result[k++] = a[i++];
}
while (j < b.length){
result[k++] = b[j++];
}
print(result);
}
看會(huì)了兩個(gè)有序數(shù)組的排序,則知道了如何實(shí)現(xiàn)歸并排序
Java代碼實(shí)現(xiàn)
private static void merge(int[] arr, int[] result, int start, int end) {
if (start >= end) return;
int center = (start + end) / 2;
int start1 = start, end1 = center;
int start2 = center + 1, end2 = end;
merge(arr, result, start1, end1);
merge(arr, result, start2, end2);
int k = start1;
while (start1 <= end1 && start2 <= end2) {
if (arr[start1] < arr[start2]) {
result[k++] = arr[start1++];
} else {
result[k++] = arr[start2++];
}
}
while (start1 <= end1) {
result[k++] = arr[start1++];
}
while (start2 <= end2) {
result[k++] = arr[start2++];
}
for (k = start; k <= end; k++) {
arr[k] = result[k];
}
print(arr);
}
快速排序
簡(jiǎn)介
快速排序（Quicksort），是一種排序算法，最壞情況復(fù)雜度：Ο(n2)，最優(yōu)時(shí)間復(fù)雜度：Ο(n log n)，平均時(shí)間復(fù)雜度：Ο(n log n)。快速排序的基本思想也是用了分治法的思想：找出一個(gè)元素X，在一趟排序中，使X左邊的數(shù)都比X小，X右邊的數(shù)都比X要大。然后再分別對(duì)X左邊的數(shù)組和X右邊的數(shù)組進(jìn)行排序，直到數(shù)組不能分割為止。
具體操作
ok,我們來(lái)看一下具體操作：
1.設(shè)置一個(gè)長(zhǎng)度為n的數(shù)組A,定義兩個(gè)變量i = 0,j = n - 1;
2.從數(shù)組中挑選出一個(gè)元素作為基準(zhǔn)元素，復(fù)制給key；
3.從j開始從后向前搜索，j--,找到比key小的值，將A[j]與A[i]互換；
4.從i 開始向后搜索，i++,找到比key大的值，將A[i]與A[j]互換；
5.遞歸的，重復(fù)2，3，4步，直到i == j ;
舉個(gè)栗子：
- 存在一個(gè)數(shù)組A：6 2 7 3 8 9 ,創(chuàng)建i = 0 ; j = 5,選擇一個(gè)基準(zhǔn)元素 k = 6
- j 從右向左查找比k小的元素，發(fā)現(xiàn)，當(dāng) j = 3 時(shí)，發(fā)現(xiàn)元素3比k小，則另A[i] 與 A[j]交換，得到3 2 7 6 8 9;
- i 從左向右進(jìn)行查找，當(dāng) i = 2時(shí)，發(fā)現(xiàn)元素 7 比k大，則另A[i] 與A[j]進(jìn)行交換，得到 3 2 6 7 8 9;
- 接著，再減小j，重復(fù)上面的循環(huán)。
- 但是我們發(fā)現(xiàn)，在本例中，一次循環(huán)后j與i就相等了，他們的下標(biāo)同時(shí)指向了2.這時(shí)候，我們就進(jìn)行分組，將3 2分為一組，7 8 9分為一組繼續(xù)上述的比較，最終得到排序好的數(shù)組。
Java代碼實(shí)現(xiàn)
public static void quickSort(int[] arr, int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start;
int right = end - 1;
while (left < right) {
while (arr[left] <= mid && left < right) {
left++;
}
while (arr[right] >= mid && left < right) {
right--;
}
swap(arr, left, right);
}
if (arr[left] >= arr[end]) {
swap(arr, left, end);
} else {
left++;
}
quickSort(arr, start, left - 1);
quickSort(arr, left + 1, end);
print(arr);
}
private static void swap(int[] arr, int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
總結(jié)
可以看出分治法的策略還是遞歸的去解決問題，基本分為三個(gè)步驟：
分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；
解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題；
合并：將各個(gè)子問題的解合并為原問題的解。
