快速选择算法

在计算机科学中,快速选择(Quickselect)是一种从无序列表找到第 k 小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的,因而也被称为霍尔选择算法。同样地,它在实际应用是一种高效的算法,具有很好的平均时间复杂度,然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。

应用场景

快速选择 是一种从无序列表找到第 k 小元素的选择算法。

基本思想

快速选择的总体思路与 快速排序 一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从 \(O(nlogn)\)\(O(n)\) ,不过最坏情况仍然是 \(O(n^2)\)

C 实现

实现一

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
void swap(int *arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

/**
* 对给定的数组区间进行划分
* @param arr 数组
* @param left 区间下限,包含arr[left]
* @param right 区间上限,包含arr[right]
* @return 返回划分后,划分基准的索引
*/
int partition(int *arr, int left, int right) {
int j = left - 1;
for (int i = left; i < right; i++) {
//以arr[right]作为划分基准
if (arr[i] <= arr[right]) swap(arr, i, ++j);
}
swap(arr, ++j, right);
return j;
}

/**
* 查找第k小元素
* @param arr 无序数组
* @param n 数组长度
* @param k 目标第k小
* @return 成功:返回第k小元素的索引
* 失败:返回-1
*/
int quickSelect(int *arr, int n, int k) {
int left = 0, right = n - 1;
while (left <= right) {
int idx = partition(arr, left, right);
if ((k - 1) == idx) return idx;
if ((k - 1) > idx) left = idx + 1;
else right = idx - 1;
}
return -1;
}

实现二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int partition(int *arr, int left, int right) {
int base = arr[left]; //以arr[left]作为划分基准
while (left < right) {
while (left < right && arr[right] >= base) right--;
arr[left] = arr[right];
while (left < right && arr[left] <= base) left++;
arr[right] = arr[left];
}
arr[left] = base;
return left;
}

int quickSelect(int *arr, int n, int k) {
int left = 0, right = n - 1;
while (left <= right) {
int idx = partition(arr, left, right);
if ((k - 1) == idx) return idx;
if ((k - 1) > idx) left = idx + 1;
else right = idx - 1;
}
return -1;
}

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void swap(int *arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

int partition(int *arr, int left, int right) {
int j = left - 1;
for (int i = left; i < right; i++) {
if (arr[i] <= arr[right]) swap(arr, i, ++j);
}
swap(arr, ++j, right);
return j;
}

int quickSelect(int *arr, int left, int right, int k) {
if (left <= right) {
int idx = partition(arr, left, right);
if ((k - 1) == idx) return idx;
if ((k - 1) > idx) return quickSelect(arr, idx + 1, right, k);
else return quickSelect(arr, left, idx - 1, k);
}
return -1;
}

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
36
37
38
39
/**
* 查找第k小元素
* @param arr 无序数组
* @param k 目标第k小
* @return 成功:返回第k小元素的索引
* 失败:返回-1
*/
public static int quickSelect(int[] arr, int k) {
int left = 0, right = arr.length - 1, idx;
while (left <= right) {
idx = partition(arr, left, right);
if ((k - 1) == idx) return idx;
else if ((k - 1) > idx) left = idx + 1;
else right = idx - 1;
}
return -1;
}

/**
* 对给定的数组区间进行划分
* @param arr 数组
* @param left 区间下限,包含arr[left]
* @param right 区间上限,包含arr[right]
* @return 返回划分后,划分基准的索引
*/
private static int partition(int[] arr, int left, int right) {
int j = left - 1;
for (int i = left; i < right; i++) {
if (arr[i] <= arr[right]) swap(arr, i, ++j);
}
swap(arr, ++j, right);
return j;
}

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

References

https://en.wikipedia.org/wiki/Quickselect

https://www.jianshu.com/p/1dbdeb07f1aa

https://www.cnblogs.com/informatics/p/5092741.html