beauty of algorithms 12 summary. sorting 2

分治思想

分治,顾明思意就是分而治之,将一个大问题分解成小的子问题来解决,小的子问题解决了,大问题也就解决了。

分治与递归的区别

分治算法一般都用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧。

归并排序

算法原理

归并的思想

先把数组从中间分成前后两部分,然后对前后两部分分别进行排序,再将排序好的两部分合并到一起,这样整个数组就有序了。

这就是归并排序的核心思想。如何用递归实现归并排序呢?

写递归代码的技巧就是分写得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。

递推公式

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 {
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)

归并排序与快速排序的区别

归并排序

先递归调用,再进行合并,合并的时候进行数据的交换。所以它是自下而上的排序方式。

何为自下而上?就是先解决子问题,再解决父问题。

快速排序

先分区,在递归调用,分区的时候进行数据的交换。所以它是自上而下的排序方式。

何为自上而下?就是先解决父问题,再解决子问题。