分治法

分治法是一种很重要的算法,也就是“分而治之”的意思,就是把一个复杂的问题分解成两个或者多个相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

比如二分搜索算法,排序算法中的快速排序和归并排序都属于分治法的一种。下面我们来看看归并排序和快速排序算法的实现。

归并排序

简介

MergeSort2
MergeSort2

(维基百科)
归并排序(Merge sort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。最优时间复杂度,O(n),平均时间复杂度为O(n log n)。由上图我们可以了解到归并排序的过程。

实例分析

以数组6 5 3 1 8 7 2 4为例。首先递归的将数组一分为2,并对子数组排序

[6, 5, 3, 1]  [8, 7, 2, 4]

[6, 5]  [3, 1]  [8, 7]  [2, 4]

[6], [5]  [4], [3]  [7], [8]  [2], [4]

然后向上回溯,将两个数组合并成有序数组

[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]

动图如下所示
MergeSort
(维基百科)

两个有序数组排序

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
/**
*
* @param a 有序数组a
* @param b 有序数组b
* @param result 结果数组
*/
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);
}

看会了两个有序数组的排序,则知道了如何实现归并排序

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
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);
}

快速排序

简介

quickSort
quickSort

(使用快速排序法对一列数字进行排序的过程——维基百科)

快速排序(Quicksort),是一种排序算法,最坏情况复杂度:Ο(n2),最优时间复杂度:Ο(n log n),平均时间复杂度:Ο(n log n)。快速排序的基本思想也是用了分治法的思想:找出一个元素X,在一趟排序中,使X左边的数都比X小,X右边的数都比X要大。然后再分别对X左边的数组和X右边的数组进行排序,直到数组不能分割为止。

具体操作

ok,我们来看一下具体操作:

1.设置一个长度为n的数组A,定义两个变量i = 0,j = n - 1;
2.从数组中挑选出一个元素作为基准元素,复制给key;
3.从j开始从后向前搜索,j–,找到比key小的值,将A[j]与A[i]互换;
4.从i 开始向后搜索,i++,找到比key大的值,将A[i]与A[j]互换;
5.递归的,重复2,3,4步,直到i == j ;

举个栗子:

  • 存在一个数组A:6 2 7 3 8 9 ,创建i = 0 ; j = 5,选择一个基准元素 k = 6
  • j 从右向左查找比k小的元素,发现,当 j = 3 时,发现元素3比k小,则另A[i] 与 A[j]交换,得到3 2 7 6 8 9;
  • i 从左向右进行查找,当 i = 2时,发现元素 7 比k大,则另A[i] 与A[j]进行交换,得到 3 2 6 7 8 9;
  • 接着,再减小j,重复上面的循环。
  • 但是我们发现,在本例中,一次循环后j与i就相等了,他们的下标同时指向了2.这时候,我们就进行分组,将3 2分为一组,7 8 9分为一组继续上述的比较,最终得到排序好的数组。

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
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;
}

总结

可以看出分治法的策略还是递归的去解决问题,基本分为三个步骤:

分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;

合并:将各个子问题的解合并为原问题的解。