分治思想
分治，顾明思意就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。
分治与递归的区别
分治算法一般都用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。
归并排序
算法原理
归并的思想
先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。
这就是归并排序的核心思想。如何用递归实现归并排序呢？
写递归代码的技巧就是分写得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。
递推公式
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件
p = r 不用再继续分解
代码实现
使用哨兵可以简化代码
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
36
37
38
39
40
41
42
43
44
| import java.util.Arrays;
public class MergeSort {
public static void merge(int[] a, int begin, int end) {
if (begin == end) {
return;
}
if (begin < end) {
int mid = (begin + end) / 2;
merge(a, begin, mid);
merge(a, mid + 1, end);
mergeAndSort(a, begin, mid, end);
}
}
public static void mergeAndSort(int[] a, int begin, int mid, int end) {
int[] left = new int[mid - begin + 2];
int[] right = new int[end - mid + 1];
for (int i = begin; i <= end; i++) {
if (i <= mid) {
left[i - begin] = a[i];
} else {
right[i - mid - 1] = a[i];
}
}
left[mid - begin + 1] = Integer.MAX_VALUE;
right[end - mid] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
int index = begin;
while (index <= end) {
a[index++] = left[i] < right[j] ? left[i++] : right[j++];
}
}
public static void main(String[] args) {
int[] a = {1, 9, 5, 7, 4, 6, 3, 8, 11, 24};
merge(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
}
|
性能分析
算法稳定性
归并排序是一种稳定排序算法。
时间复杂度
归并排序的时间复杂度是O(nlogn)。
空间复杂度
归并排序算法不是原地排序算法，空间复杂度是O(n)
因为归并排序的合并函数，在合并两个数组为一个有序数组时，需要借助额外的存储空间
快速排序
一般情况下，快速排序被认为是最快的排序算法（人如其名啊），因此可以说是最常用的排序算法，并受大多数公司的青睐，是一定要熟练掌握的。
算法原理
快排的思想
如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。然后遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将povit放到中间。
经过这一步之后，数组p到r之间的数据就分成了3部分，前面p到q-1之间都是小于povit的，中间是povit，后面的q+1到r之间是大于povit的。
根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。
递推公式
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件
p >= r
代码实现
左右两个指针分别向左向右移动，取最后一位做临界值，左边遇到比这个值大的，就交换，换反方向指针比较，遇到比这个值小的，再次交换。
参考这里
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
36
37
38
39
40
41
42
43
| import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] a, int begin, int end) {
if (end <= begin) {
return;
}
int i = begin;
int j = end;
int tmp = a[end];
boolean tag = true;
while (i != j) {
if (tag) {
if (a[i] <= tmp) {
i++;
continue;
} else {
a[j] = a[i];
j--;
tag = false;
}
} else {
if (a[j] >= tmp) {
j--;
continue;
} else {
a[i] = a[j];
i++;
tag = true;
}
}
}
a[i] = tmp;
quickSort(a, begin, i - 1);
quickSort(a, i + 1, end);
}
public static void main(String[] args) {
int[] a = {5, 7, 8, 2, 6, 125, 6, 41, 341, 34, 63, 28, 97};
quickSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
}
|
性能分析
算法稳定性
快速排序是不稳定的排序算法。
时间复杂度
如果每次分区操作都能正好把数组分成大小接近相等的两个小区间，
那快排的时间复杂度递推求解公式跟归并的相同。快排的时间复杂度也是O(nlogn)。
如果数组中的元素原来已经有序了，快排的时间复杂度就是O(n^2)。
前面两种情况，一个是分区及其均衡，一个是分区极不均衡，
它们分别对应了快排的最好情况时间复杂度和最坏情况时间复杂度。
T(n)大部分情况下是O(nlogn)，只有在极端情况下才是退化到O(n^2)。
空间复杂度
快排是一种原地排序算法，空间复杂度是O(1)
归并排序与快速排序的区别
归并排序
先递归调用，再进行合并，合并的时候进行数据的交换。所以它是自下而上的排序方式。
何为自下而上？就是先解决子问题，再解决父问题。
快速排序
先分区，在递归调用，分区的时候进行数据的交换。所以它是自上而下的排序方式。
何为自上而下？就是先解决父问题，再解决子问题。
