选择问题—算法导论(10)

2015年09月27日 14:31

1. 写在最前面

这一篇探讨选择问题。它的提法是：

输入：一个包含n个（互异）数的序列A和一个数i（1≤i≤n）。 输出：元素x（x∈A），且A中有i-1个元素比x小。

简单的说，就是在A中找到第i小的数。

2. 期望为线性时间的选择算法

算法描述与实现

先给出算法的伪代码描述：

其主要思想与我们前面介绍的快速排序——算法导论(8)基本一样，只是在该问题中，每次递归时，只用考虑第i小的数可能出现的分组。

下面给出 Java 实现代码：

public static void main(String[] args) {
    // 1, 2, 3, 4, 5, 7, 9
    int[] array = new int[] { 3, 2, 7, 4, 5, 9, 1 };
    System.out.println(randomizedSelect(array, 0, array.length - 1, 5));
}

public static int randomizedSelect(int[] array, int start, int end, int i) {
    if (start == end) {
        return array[start];
    }
    int q = randomPartition(array, start, end);
    int k = q - start;
    if (k == i) {
        return array[q];
    } else if (i < k) {
        return randomizedSelect(array, start, q , i);
    } else {
        return randomizedSelect(array, q , end, i-k);
    }
}

/**
 * 重排array，并找出“临界”位置的索引
 *
 * @param array 待重排数组
 * @param start 待重排子数组的起始索引
 * @param end 待重排子数组的结束索引
 * @return
 */
public static int partition(int[] array, int start, int end) {
    int position = start - 1;
    int base = array[end];
    for (int i = start; i < end; i++) {
        if (array[i] <= base) {
            position++;
            int temp = array[position];
            array[position] = array[i];
            array[i] = temp;
        }
    }
    int temp = array[position + 1];
    array[position + 1] = array[end];
    array[end] = temp;
    return position + 1;
}

public static int randomPartition(int[] array, int start, int end) {
    int random = (int) (Math.random() * ((end - start) + 1)) + start;
    int temp = array[random];
    array[random] = array[end];
    array[end] = temp;
    return partition(array, start, end);
}

算法分析

可以证明，上述算法的期望运行时间为 $\Theta(n)$。证明略。