关于快排和归并的思考

归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是 O (n)。正因为此它也没有快排应用广泛。快速排序算法虽然最坏情况下的时间复杂度是 O (n²),但是平均情况下时间复杂度都是 O (nlogn)。且快速排序算法时间复杂度退化到 O (n²) 的概率非常小,我们可以通过合理地选择基准值来避免这种情况。

什么是数组的逆序度

如果用概率论方法定量分析平均时间复杂度,涉及的数学推理和计算就会很复杂。我们其实还有一种思路,通过 有序度 逆序度 这两个概念来进行分析。有序度是指数组中具有有序关系的元素对的个数,如下图所示:

mark

所以对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是 n\*(n-1)/2,也就是 15。我们把这种完全有序的数组的有序度叫作 满有序度 。逆序度的定义正好跟有序度相反(默认从小到大为有序),所以满有序度 - 有序度 = 逆序度。

求数组的逆序度

数组的逆序度也就是数组的逆序对的个数,如果要求出来也是比较简单,直接暴力解法就可以,检查每一个数对,但是这样的时间复杂度为 O (n²)。我们能否使用它更快捷的方法呢?其实是有的,那就是我们用归并排序的思路思路来解决这个问题,时间复杂度降到 O (nlogn)。

mark

如上图所示,对于归并排序,红线两边都是已经排好序的数组,此时做归并需要把 1 给挪到 2 的位置,意思就是 1 这个元素比 2-8 这一部分元素都大,所以无序度直接 + 4 就达到了省时间的目的。接下来的步骤如图所示:

mark

2 会放在 2 的位置上,这也就意味着 2 比 4 以及 4 以后的元素都要小,那么 2 和 4 以及 4 以后的元素都组成了顺序对。当归并完成以后就求得了数组的逆序度:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//merge 函数求出在 arr [l...mid] 和 arr [mid+1...r] 有序的基础上,arr [l...r] 的逆序数对个数 
private static long merge(int[] arr, int l, int mid, int r) {

int[] aux = Arrays.copyOfRange (arr, l, r+1);

// 初始化逆序数对个数 res = 0
long res = 0L;

// 初始化,i 指向左半部分的起始索引位置 l;j 指向右半部分起始索引位置 mid+1
int i = l, j = mid+1;
for(int k = l ; k <= r; k++ ){
// 如果左半部分元素已经全部处理完毕
if(i > mid){
arr [k] = aux [j-l];
j++;
}
// 如果右半部分元素已经全部处理完毕
else if(j > r){
arr [k] = aux [i-l];
i++;
}
// 左半部分所指元素 <= 右半部分所指元素
else if( aux [i-l] < aux [j-l]){
arr [k] = aux [i-l];
i++;
}
else{
// 右半部分所指元素 < 左半部分所指元素
arr [k] = aux [j-l];
j++;
// 此时,因为右半部分 k 所指的元素小
// 这个元素和左半部分的所有未处理的元素都构成了逆序数对
// 左半部分此时未处理的元素个数为 mid - j + 1
res += (long)(mid - i + 1);
}
}

return res;
}

// 求 arr [l..r] 范围的逆序数对个数
private static long solve(int[] arr, int l, int r) {
if (l >= r)
return 0L;

int mid = l + (r-l)/2;
// 求出 arr [l...mid] 范围的逆序数
long res1 = solve (arr, l, mid);

// 求出 arr [mid+1...r] 范围的逆序数
long res2 = solve (arr, mid + 1, r);

return res1 + res2 + merge (arr, l, mid, r);
}

public static long solve(int[] arr){
int n = arr.length;
return solve (arr, 0, n-1);
}

求数组中第 N 小的元素

其实这个问题是一个明显的 Top K 问题,但是我们除了用堆还能用其他方法吗?其实快速排序也可以解决这个问题,我们回顾一下快速排序的过程(《 快速排序及其优化 》),其实就是通过基准值每次把数组进行划分,我们只需要保留存在第 N 大的元素的那一部分即可,这么处理的话时间复杂度是 O (n),复杂度 = n + n/2 + n/4 + n/8 + … ,所有看成是 O (n) 或者 O (2n) 的时间复杂度,但是我们需要注意的是需要使用随机化法,来确定基准值。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class QuickSortTopK {
// 对 arr [l...r] 部分进行 partition 操作
// 返回 p, 使得 arr [l...p-1] < arr [p] ; arr [p+1...r] > arr [p]
//partition 过程,和快排的 partition 一样
private static int partition(int[] arr, int l, int r){
// 随机在 arr [l...r] 的范围中,选择一个数值作为标定点 pivot
swap (arr, l , (int)(Math.random ()*(r-l+1))+l );

int v = arr [l];
int j = l; //arr [l+1...j] < v ; arr [j+1...i) > v
for( int i = l + 1 ; i <= r ; i ++ )
if( arr [i] < v){
j ++;
swap (arr, j, i);
}

swap (arr, l, j);

return j;
}

// 求出 nums [l...r] 范围里第 k 小的数
private static int solve(int[] nums, int l, int r, int k){
if( l == r ) return nums [l];

//partition 之后,nums [p] 的正确位置就在索引 p 上
int p = partition (nums, l, r);

// 如果 k == p, 直接返回 nums [p]
if( k == p )
return nums [p];
// 如果 k < p, 只需要在 nums [l...p-1] 中找第 k 小元素即可
else if( k < p )
return solve ( nums, l, p-1, k);
else// 如果 k > p, 则需要在 nums [p+1...r] 中找第 k-p-1 小元素
// 注意:由于我们传入__selection 的依然是 nums, 而不是 nums [p+1...r],
// 所以传入的最后一个参数依然是 k, 而不是 k-p-1
return solve ( nums, p+1, r, k );
}

// 寻找 nums 数组中第 k 小的元素
// 注意:在我们的算法中,k 是从 0 开始索引的,即最小的元素是第 0 小元素,以此类推
// 如果希望我们的算法中 k 的语意是从 1 开始的,只需要在整个逻辑开始进行 k-- 即可,可以参考 solve2
public static int solve(int[] nums, int k) {
assert nums != null && k >= 0 && k < nums.length;
return solve (nums, 0, nums.length - 1, k);
}

private static void swap(int[] arr, int i, int j) {
int t = arr [i];
arr [i] = arr [j];
arr [j] = t;
}

// 测试 Selection
public static void main(String [] args) {
// 生成一个大小为 n, 包含 0...n-1 这 n 个元素的随机数组 arr
int N = 10;
int[] arr = SortTestHelper.generate (N, 0, N);
for(int i: arr) System.out.print (i + " ");
System.out.println ();
int solve = solve (arr, 3);
System.out.println (solve);
}
}