Keep It Simple, Stupid

快速选择算法

发表于 更新于 分类于 ， Valine：
本文字数： 508 阅读时长 ≈ 1 分钟

在计算机科学中，快速选择（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