题目内容

给定一个线性序列集，要求使用分治法求出其中指定的第 K 小的数的值和位置，如给定 n 个元素和一个整数 i ，1 ≤ i ≤ n ，输出这 n 个元素中第 i 小元素的值及其位置。

问题分析

有如下几种方法：

  • 将n个数排序(比如快速排序或归并排序)，选取排序后的第k个数，时间复杂度为O(logn)
  • 维护一个k个元素的最大堆，存储当前遇到的最小的k个数，时间复杂度为O(nlogk)。这种方法同样适用于海量数据的处理
  • 部分的快速排序（快速选择算法），每次划分之后判断第k个数在左右哪个部分，然后递归对应的部分，平均时间复杂度O(n)。但最坏情况下复杂度为O(n2)
  • 线性时间选择算法，修改快速选择算法的主元选取规则，使用中位数的中位数的作为主元，最坏情况下时间复杂度为O(n)

这里选择线性时间选择算法。

算法的思路是：

  1. 首先把数组按5个数为一组进行分组，最后不足5个的忽略。对每组数进行排序（如插入排序）求取其中位数。
  2. 把上一步的所有中位数移到数组的前面，对这些中位数递归调用线性时间选择算法求得他们的中位数。
  3. 将上一步得到的中位数作为划分的主元进行整个数组的划分。
  4. 判断第k个数在划分结果的左边、右边还是恰好是划分结果本身，前两者递归处理，后者直接返回答案。

时间复杂度分析

​ 当n < 75时，时间复杂度很低，近似于常数, n大于75时，划分时以5个元素为一组求取中位数，共得到n/5个中位数，再递归求取中位数，复杂度为T(n/5)，剩余要处理的最大规模变为3n/4，加上多次线性扫描，其时间复杂度为C2，所以可以得到递推式：

T(n)≤{C1n<75C2n+T(n/5)+T(3n/4)n≥75T(n) \le \left\{ \begin{array}{c} C_1 & n < 75 \\ C_2n + T(n/5) + T(3n/4) & n \ge 75 \end{array} \right.

可以得到 T(n)=O(n)T(n) = O(n)

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Type Select(Type a[], int p, int r, int k) {
    if (r - p < 75) {
        用某个简单排序算法对数组a[p:r] 排序;
        return a[p + k - 1];
    }
    // (r - p - 4) / 5 == (r - p + 1) / 5 - 1, 即为最后一个i的下标
    for (int i = 0; i <= (r - p - 4) / 5; i++)
        将a[p + 5 * i] 至a[p + 5 * i + 4] 的第3小元素 与a[p + i] 交换位置
    // 找中位数的中位数
    Type x = Select(a, p, p + (r - p - 4) / 5, (r - p - 4) / 10);
    int i = Partition(a, p, r, x);
    int j = i - p + 1;
    if (k <= j)
        return Select(a, p, i, k);
    else
        return Select(a, i + 1, r, k - j);
}

其中

1
2
3
4
5
6
7
8
9
10
11
12
13
int Partition(int a[], int p, int r, int x) {
    int i = p, j = r + 1;
    while(true) {
        while(a[++i] < x && i < r);
        while(a[--j] > x);
        if(i >= j) 
            break;
        swap(a[i], a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}