十万个数找到前十个

这是考研题中能够数据结构中的一道题，要求时间复杂度尽可能的小，因此我们使用简单排序或者是快速排序进行完全排序后输出前几个是完全不可以的，时间复杂的会很高，这里我选择使用线性选择的方式。

算法思路

使用线性选择 ，选择到第十个数据，因为线性选择是以快排为基础的，因此当我们找到了这第十个数据。那么我们此时生成的数组第十个数据前边的比他小，前十个就是在这个乱序中.

• 先使用线性选择选择到第十个数据
• 将这个数组的前十个数据进行排序（随意，可以使用简单排序）
• 输出结果

验证，因为我们的数组是随机生成的 无法保证找到的数据是正确的（可能某个程序错误将数组更改），因此我们需要在生成数组的时候将数组存储到文件中，然后使用全排序对齐进行排序，之后输出前十个来验证是否和我们使用线性选择找到的数据相同。

程序实践

这里我们开一个文件把我们的随机生成的数组储存起来，以方便以后的验证使用，此时就需要用的文件的读取知识

import com.dwx.passage2.RandomizedSelect;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class fisrtTen {
    public static void main(String[] args) throws IOException {
        //成功一个有十万个数据的数组 用随机数产生
        int[] a = new int[100000];
        int length = a.length;
        int i,j,k;

        for (i=0;i<length;i++){
            //产生10万个随机数
            a[i] = (int)(Math.random()*1000000)+10000;
        }
        //我们可以将这个数组先存放到file中 到其他的程序进行测试
        String fileName = "shiwan.txt";
        File file = new File(fileName);
        FileWriter fileWriter = null;
        try {
            fileWriter = new FileWriter(file);
        } catch (IOException e) {
            e.printStackTrace();
        }
        BufferedWriter writer = new BufferedWriter(fileWriter);
        writer.write(Integer.toString(a.length));
        for (int i1 : a) {
            writer.newLine();
            writer.write(Integer.toString(i1));
        }
        writer.flush();
        writer.close();

        //选择前十个
        //调用线性选择程序
        RandomizedSelect select = new RandomizedSelect();
        select.setList(a);
        int i1 = select.RandomizedSelect(0, a.length - 1, 10);
        System.out.println("第十个数据是:"+i1);
        int[] list = select.getList();
        //对前十个数据进行排序
        simpleSort(list,0,9);
        for (i=0;i<10;i++){
            System.out.println(list[i]+"\t");
        }
    }

    //我们这里需要一个简单排序
    public static void simpleSort(int[] e,int start,int end){
        int i;
        int j;
        int temp;
        int k;
        i = start;
        for (i=start;i<=end;i++){
            temp = e[i];
            k = i;
            for (j=i;j<=end;j++){
                //寻找每次循环的最小值
                if (e[j]<temp){
                    temp = e[j];
                    k = j;
                }

            }
            //进行交换 把最小值放到合适的位置
            e[k] = e[i];
            e[i] = temp;
        }
    }
}

---

线性的算则：这里我是用的是随机选择

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;
    }
    //交换数据函数
    public void Swap(int i,int j){
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

检验得程序：

import com.dwx.file.MyFileReader;

import java.io.File;
import java.util.List;

public class sortTest {
    public static void main(String[] args) throws Exception {
        //这里我们对我们存储的数据进行最简单的排序
        int[] a = new int[100000];
        int i;
        //读取我们的数据
        String fileName = "shiwan.txt";
        File file = new File(fileName);
        MyFileReader reader = new MyFileReader();
        List<Object> objects = reader.MyFilerReader(file);
        //第一个数据表示个数 可以不读
        for (i=0;i<a.length;i++){
            a[i] = Integer.parseInt((String) objects.get(i+1));
        }
        //对数组进行排序
        simpleSort(a,0,a.length-1);
        //输出前十个
        for (i=0;i<10;i++){
            System.out.println((i+1)+"================》"+a[i]);
        }


    }
    public static void simpleSort(int[] e,int start,int end){
        int i;
        int j;
        int temp;
        int k;
        i = start;
        for (i=start;i<=end;i++){
            temp = e[i];
            k = i;
            for (j=i;j<=end;j++){
                //寻找每次循环的最小值
                if (e[j]<temp){
                    temp = e[j];
                    k = j;
                }

            }
            //进行交换 把最小值放到合适的位置
            e[k] = e[i];
            e[i] = temp;
        }
    }
}

经过检验，我们可以发现我们的程序是正确的

而且要比使用简单排序的全排列块的多。

Donate