快速排序

原理不再赘述,这里给出一个快速排序的例子。

快速排序

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
public static void quicksort(int[] array) {
quicksort(array, 1, array.length - 1);
}
// 方法重载用于指定head、tail
public static void quicksort(int[] array, int head, int tail) {
if(head > tail)
return;
// standard是每次比较范围的起点,也是比较标准(图中被圈中的数)
int standard = head - 1;
// limit是每次比较范围的终点
int limit = tail;
while(head <= tail) {
while(head <= tail && array[head] <= array[standard])
head++;
while(head <= tail && array[tail] > array[standard])
tail--;
if(head < tail) {
int temp = array[head];
array[head] = array[tail];
array[tail] = temp;
}
}
int temp = array[standard];
array[standard] = array[head - 1];
array[head - 1] = temp;
// 递归实现<=standard和>standard两段的快速排序
quicksort(array, standard + 1, head - 2);
quicksort(array, head + 1, limit);
}

借助快速排序

1:

找出给定整形数组中最小的k个数。

对数组进行快速排序(从大到小排序,不仅仅是快速排序),数组前k个元素即所求。

1
2
3
4
5
6
7
8
public static void minK_else(int[] array, int k) {
if(k > array.length)
return;
quicksort(array);
for(int i = 0; i < k; i++)
System.out.print(array[i] + " ");
}

进一步改善,没有必要进行一次完整的快速排序。

如,找出{49, 12, 36, 76, 24, 49, 54, 93, 34}中最小的5个数,一次比较结束后,数组中的前5个元素已经是最小的5个数。如果k > 5,可以进一步比较后一段,如果k < 5,则缩小前一段的比较范围。一定程度上可以降低递归次数。

与快速排序类似,区别在于一次比较结束后,不是立即递归进行下一次比较,而是先判断给定的k值是否已经被满足,未满足条件再进行下一次递归。

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
public static void minK(int[] array, int k) {
if(k <= 0 || k > array.length)
return;
int standard = array[0];
int head = 1;
int tail = array.length - 1;
while(head <= tail) {
while(head <= tail && array[head] <= standard) {
head++;
}
while(head <= tail && array[tail] > standard) {
tail--;
}
if(head < tail) {
int temp = array[head];
array[head] = array[tail];
array[tail] = temp;
}
}
int temp = array[0];
array[0] = array[head - 1];
array[head - 1] = temp;
// 已经可以确定最小的k(或k - 1)个数
if(head == k || head - 1 == k) {
for(int i = 0; i < k; i++)
System.out.print(array[i] + " ");
}
// 需要进一步缩小前一段的比较范围
else if(head - 1 > k) {
int[] part = new int[head - 1];
System.arraycopy(array, 0, part, 0, part.length);
minK(part, k);
}
// 需要在后一段继续比较
else {
for(int i = 0; i < head; i++)
System.out.print(array[i] + " ");
int[] part = new int[array.length - head];
System.arraycopy(array, head, part, 0, part.length);
minK(part, k - head);
}
}
2:

在由n个正整数组成的集合S中,找出最大元素M,满足M = A + B,其中A、B都是集合S中的元素。

LeetCode Solution – Two Sum给出了利用HashMap判断集合中是否存在两个数,使其相加的和为给定的target。

这里采用类似的方法,先对集合S进行快速排序,再从S中的最大值开始遍历,使用HashMap判断是否存在M满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxValueInS(int[] S) {
// 对S进行快速排序
quicksort(S);
// 从S中最大值开始遍历
for(int j = S.length - 1; j >= 2; j--) {
int M = S[j];
java.util.HashMap<Integer, Integer> map = new java.util.HashMap<Integer, Integer>();
for(int i = j - 1; i >= 0; i--) {
if(map.containsValue(S[i]))
return M;
else
map.put(S[i], M - S[i]);
}
}
return 0;
}