线性时间选择

选择一个无序整数列中的第i小

基本思想

利用快速排序的思想 因为快速排序特点是 每一次排序一定能够把一个值给确定位置，因此这里如果我们给确定位置的值和我们要找的值一样 那么我们成功了

RandomSelect

package com.dwx.passage2;

public class RandomizedSelect {

    //正常来说 我们操作的都是整数数组
    private int list[];
    //我们使用的是private私有对象 因此需要编写get/set方法来设置和获取值

    public int[] getList() {
        return list;
    }

    public void setList(int[] list) {
        this.list = list;
    }

    //快速排序的思路是将第一个作为端点 但是我们这里使用一个随机数来获得端点
    /*
    参数表：
    start：列表要查询的开始
    end：列表查询的结束
    find：我们要查询的第几小
     */

    public int RandomizedSelect(int start,int end,int find){
        //编写程序结束程序
        //如果开始等于结束 我们没有什么课选的了 就选择到了合适的数据
        if (start==end){
            //这个就是我们找到的第几小的结果
            return list[start];
        }
        int i = RandomQuickSort(start,end);
        //比较我们得到的这个第几小和我们的目标小又什么区别
        //如果i大 则说明我们要找的find在划分后的后边
        //则将我们的起始地址设置为i+1,结束还是end，此时我们要找find-i小
        //注意 我们这里的j 因为 我们的start 不一定就是从零开始的 因此 我们选择后的第几小 就需要用find-j
        int j = i-start+1;
        if (find<=j){
            return RandomizedSelect(start,i,find);
        }else {
            return RandomizedSelect(i+1,end,find-j);
        }
    }


    //这个程序是对我们需要的list的一段进行一次快排 二我们快排的结果是随机的 通过random来获得我们的基准元素
    public int RandomQuickSort(int start,int end){
        //我们这里只需要一个开始和一个结束
        //获得一个随机数 在start和end之间
        //我们这里的随机数要设置好
        int n = (int)(Math.random()*100)%(end-start)+start;
        System.out.println("这里我们将第"+n+"个元素作为基准元素");
        //将我们的基准元素存储起来

        int t = list[n];
        list[n] = list[start];
        list[start] = t;
        int i,j;
        //我们准备进行快排
        i = start;
        j = end;
        //快速排序的思想就是把比基准元素小的都放在左边
        //把比基准元素大的都放在右边 然后把基准元素归位
        while (i != j){
            //先让右哨兵动 找到合适数据后才停止
            while (list[j]>=t && j>i){
                j--;
            }
            //说明右哨兵已经选择好了 使左哨兵开始动
            while (list[i]<=t && i<j){
                i++;
            }
            //两个哨兵都找到了 交换数据
            if (i<j) {
                int temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }

        }
        //将我们的基准元素放到合适的地方
        list[start] = list[i];
        list[i] = t;
        //我们找到的i就是我们这一次找到的目的元素所在的位置(即第几小)
        return i;
    }
}

实现类：

import com.dwx.passage2.RandomizedSelect;

import java.util.Scanner;

public class RandomSelectTest {
    public static void main(String[] args) {
        RandomizedSelect select = new RandomizedSelect();
        //选择我们的一个list
        int[] list = new int[]{13,45,85,63,21,54,96,35,74,84,9,6,3,8,5};

        System.out.println("我们的无序数组的长度"+list.length);
        select.setList(list);
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入我们要选择第几小:");
        int find = scanner.nextInt();
        int i = select.RandomizedSelect(0, list.length - 1, find);
        System.out.println("我们找到的数据"+i);

        System.out.println("====================================");
        for (int i1 : list) {
            System.out.print(i1+"\t");
        }
        System.out.println();
        System.out.println("====================================");
        //这里设置一个简单排序来检测结果的正确性
        int[] query = query(list);

        for (int i1 : query) {
            System.out.print(i1+"\t");
        }
        System.out.println();
        System.out.println("理论上我们的目标值"+list[find-1]);

    }

    //下边我们写一个冒泡排序 把我们的list进行一个排序 看看是否我们的答案和我们的找到的数据相同
    public static int[] query(int[] list){
        //冒泡排序
        int i;
        int j;
        int temp;
        //冒泡排序的思想是 每次找到一个最小的放在应该最小的位置
        int min;
        for (i=0;i<list.length;i++){
            min = i;
            for (j=i;j<list.length;j++){
                if (list[j] < list[min]){
                    //记录找到的最小的数的下标
                    min = j;
                }
            }
//            if (i!=min) {
                temp = list[min];
                list[min] = list[i];
                list[i] = temp;
//            }

        }
        return list;
    }
}

这里我们还加装了一个一般排序来检测是否我们实现了

写这个算法真考研逻辑思维能力

Donate