排序算法之期望为线性时间的选择算法（Java 版本）

news/2025/2/26 3:31:22

在了解选择算法前，我们先熟悉一个名词顺序统计量。在集合中，第 i 个数序统计量指的是该集合第 i 小元素。
而选择算法处理的问题是：在 n 个元素组成的集合中，查找第 i 个顺序统计量的问题。假如i=3，即需要查找集合中第 3 小的元素

基本思想

利用分治思想，以快速排序中的分区算法为基础，根据要查找的顺序统计量的位置递归求解。

问题分解：利用分区算法（见快速排序章节）将数组分区，判断 i 的分区位置，递归进行。
问题处理：当分区样本所在位置等于 i 时，返回结果。

代码实现

与快速排序中分区算法不同的是此处的分区算法加入了随机取样功能，具体请看代码。

    /**
     * 获取数组任意位置的顺序统计量
     * @param array 输入数组
     * @param pos 查询位置
     * @param start 起始位置
     * @param end 结束位置
     * @return 元素值
     */
    private static int randomSelection(int[] array, int pos, int start, int end) {
        //获取随机分区的样本位置
        int mid = randomPartition(array, start, end);
        //递归结束点，当要获取的 pos=mid 时
        if (pos == mid) {
            return array[mid];
        }
        System.out.println("start:" + start + "|end:" + end + "|pos:" + pos + "|mid:" + mid);
        //递归情况
        if (pos < mid) {
            return randomSelection(array, pos, start, mid - 1);
        } else {
            return randomSelection(array, pos, mid + 1, end);
        }
    }

    /**
     * 随机分区
     * @param array 分区数组
     * @param start 起始位置
     * @param end 结束位置
     * @return 样本位置
     */
    private static int randomPartition(int[] array, int start, int end) {
        //计算随机样本位置
        int samplePos = random(start, end);
        //将随机样本放到数组尾部
        int temp = array[end];
        array[end] = array[samplePos];
        array[samplePos] = temp;

        int sample = array[end];
        //左侧区域默认为空
        int leftEnd = start - 1;
        //检测到小于样本值的数据，放入左侧区域
        for (int i = start; i < end; i++) {
            if (array[i] <= sample) {
                leftEnd++;
                temp = array[leftEnd];
                array[leftEnd] = array[i];
                array[i] = temp;
            }
        }
        //将样本中放到中间区域
        temp = array[end];
        array[end] = array[leftEnd + 1];
        array[leftEnd + 1] = temp;

        return leftEnd + 1;
    }