文档章节

寻找最大的K个数(一):快排和选择

zongjh
 zongjh
发布于 2017/05/12 12:29
字数 1438
阅读 31
收藏 0

接下来两天,和大家一起聊一聊这个问题:寻找最大的K个数。

 

问题如下:

有很多个无序的数(我们这里假设为正整数),而且各不相等,怎么选出最大的K个数。

 

例如:2,5,7,1,3,9,3,6,7,8,5

最大的5个数为:7,9,6,7,8

 

相信很多人都被这个问题给虐过。

 

当你还是一个菜鸟的时候,你以为很简单。so easy!

 

声明一个数组,数组从大到小排序,然后取前K个数,不就结了。so easy!

 

如果数很大呢,例如1000个,那就声明大小为1000的数组。还是 so easy!

 

如果有1亿个呢?还要声明大小为1亿的数组吗?

 

额,这个,我要想想!

 

下面介绍的解法没有好坏之分,不同的情况选择不同的解法,才是一个好程序员。

 

文章会分为三个篇幅来介绍:

第一部分:常规解法,包括快速排序,选择排序。

第二部分:第一部分的优化版。

第二部分:是处理大数据量的解法,包括使用最小堆排序,还有一个终极算法,时间复杂度为线性(不过需要有前提条件)。

 

解法一:使用快速排序或选择排序

 

将数组排序,是我们能够想到的第一个解决方案。

 

在所有的排序中快速排序和堆排序时间复杂度是最低的。

 

快排思路:使用快速排序,将数组全排序,这样我只需要从后向前查找K的数,即为我们要找的前K个最大的数。

 

PS: 这里默认数组长度都比K大

 

下面是快速排序的代码:

 

package com.xylx.utils.selectK;

public class QuickSortSelectK {
    public static void main(String[] args) {
        int[] arr = Constans.getLengthArr(100);
        System.out.println("排序前:");
        Constans.printArr(arr);
        quickSort(arr, 0, arr.length-1);
        System.out.println("排序后:");
        Constans.printArr(arr);
        System.out.println("排序是否正确: "+Constans.isOk(arr));
        Constans.selectK(arr);
    }

    //从后向前查找
    /**
     * 要点:从后向前查找,
     * 移动数据位置不要忘记判断条件
     * 一次排序后,数组会一分为二,分别是start到left-1 和 right+1<end
     *  记住,分别进行快排的时候,不要忘记添加判断条件
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr, int start, int end){
        int left = start;
        int right = end;
        int key = arr[left];
        while (left < right) {
            while (left < right && arr[right] > key) {
                right--;
            }
            if (left < right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
                left++;
            }
            while (left < right && arr[left] < key) {
                left++;
            }
            if (left < right) {
                int tmp = arr[right];
                arr[right] = arr[left];
                arr[left] = tmp;
                right--;
            }
        }
        if (start < left-1) {
            quickSort(arr, start, left-1);
        }
        if (right + 1 < end) {
            quickSort(arr, right+1, end);
        }
    }
}

关于快速排序想必大家也都知道,所以就不多说了。

 

这个类需要一个辅助类,辅助类主要是用来生成给定大小的数组,校验排序是否正确,以及数组输出。源码如下:

package com.xylx.utils.selectK;
import java.util.Random;
/**
 */
public class Constans {
    private static int JI_ZHUN = 1000; //数组元素随机数的基数
    private static int K = 10; 
    /**
     * 生成长度为length的int类型数组
     * @param length
     * @return
     * @throws Exception
     */
    public static int[] getLengthArr(int length) {
        if (length<1) {
            length = 100;
        }
        int[] arr = new int[length];
        Random random = new Random();
        for (int i=0; i<length; i++) {
            arr[i] = random.nextInt(JI_ZHUN);
        }
        return arr;
    }
    public static void printArr(int[] arr) {
        System.out.println("数组输出:\n");
        for (int i=0; i<arr.length; i++) {
            System.out.print(arr[i]+"    ");
        }
        System.out.println();
    }
    /**
     * 校验排序是否正确
     * @param arr
     * @return
     */
    public static boolean isOk(int[] arr) {
        for (int i=0; i<arr.length-1; i++) {
            if (arr[i+1] < arr[i]) {
                return false;
            }
        }
        return true;
    }
    public static void selectK(int[] arr) {
        System.out.println("最大的K个数:");
        for (int i=arr.length-K; i<arr.length; i++) {
            System.out.print(arr[i]+"    ");
        }
        System.out.println();
    }
}

 

上面的代码都是自己写的并且经过测试,拷贝下来就能直接运行。

 

你一定能够注意到,上面的快速排序是将所有的数据进行了排序,而我们需要的只是前K个数,也就是我们多排了N-K个数。假设数组长度为N。

 

那么怎么避免多做N-K个数的排序呢?我们可以选择选择排序算法。

 

选择排序:每一次从待排序数据中选择最小(最大)的一个数,放在序列的起始(结束)位置,直到所有待排序数据全部排序完成。这里需要注意:当排完前K个数后,我们就要终止排序。

 

代码如下(辅助类同上):

 

package com.xylx.utils.selectK;

/**
 * Created by baidu on 17/5/8.
 */
public class SelectSortSelectK {
    public static void main(String[] args) {
        int arr[] = Constans.getLengthArr(100);
        System.out.println("排序前:");
        Constans.printArr(arr);
        selectSort(arr);
        System.out.println("排序后:");
        Constans.printArr(arr);
        Constans.selectK(arr);
    }

    /**
     * 注意要点:
     *  注意下标的位置,以及数据的及时复位
     * @param arr
     */
    public static void selectSort(int[] arr) {
        int index = arr.length-1;
        int tmp = Integer.MIN_VALUE;
        int tmpIndex = 0;
        for (int i=arr.length-1; i>0; i--) {

            for (int j=0; j<=i; j++) {
                if (arr[j] > tmp) {
                    tmp = arr[j];
                    tmpIndex = j;
                }
            }
            arr[tmpIndex] = arr[index];
            arr[index] = tmp;
            if (arr.length-index == Constans.K) {
                break;
            }
            tmp = Integer.MIN_VALUE;
            index--;
        }
    }
}

前面快速排序的时间复杂度为O(N*log2N),选择排序的时间复杂度为O(N*K)。至于选择快速排序还是选择排序需要看K的大小。也就是计算下面的公式:

N*log2N>N*K

 

明天我们会介绍另外两个算法:快速排序的优化版,利用二分搜索策略。

 

快速排序的优化版:

一次快速排序会将数组分位两部分Sa和Sb。Sb的任意值都比Sa的任意值要大。所以就会有两种情况出现:

1,Sb.length>=K,我们只需要关心Sb就好了

2,Sb.length<K,我们关心的是Sb和Sa中K-Sb.length个最大的数

 

二分搜索策略:寻找最大的K个数,也就是寻找这些数中最小的那个值。

 

喜欢聊技术或者聊观点,可以加入公号:【花生读书汇】

一起:励志,成长,学习,分享。

【花生读书汇】

© 著作权归作者所有

zongjh
粉丝 1
博文 39
码字总数 12405
作品 0
东城
程序员
私信 提问
排序总结(不断更新)

排序法 最好时间分析 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n)(改进的冒泡排序) O(n2) O(n2) 稳定 O(1) 快速排序 O(nlog2n) O(n2) O(nlog2n) 不稳定 O(log2n)~O(n) ...

Hosee
2015/10/23
786
0
数据结构学习(一)

数据结构与算法 1. 链表与数组。 2. 队列和栈,出栈与入栈。 3. 链表的删除、插入、反向。 4. 字符串操作。 5. Hash表的hash函数,冲突解决方法有哪些。 6. 各种排序:冒泡、选择、插入、希尔...

技术小甜
2017/11/16
0
0
双枢轴快排(JDK7快排)(译文)

双枢轴快排算法 Vladimir Yaroslavskiy iaroslavski@mail.ru 第一版:2009-02-16 最后更新:2009-09-11 译者:黑狗 Email:blackdog@gmail.com 介绍 在计算机科学中数据排序是最基础的一个问题...

黑狗
2012/08/29
0
0
深度剖析八大经典排序算法—C++实现(通俗易懂版)

内容会持续更新,有错误的地方欢迎指正,谢谢! 引言 该博客的示例代码均以递增排序为目的~ 学习建议:切忌看示例代码去理解算法,而是理解算法原理写出代码,否则会很快就会忘记。 算法分类 ...

billcyj
2017/11/06
0
0
【Top K 问题】[Leetcode-215] Kth Largest Element in an Array 数组中第K大的数

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xidiancoder/article/details/77781379 0. 本文概要 Top K问题在大数据领域非常普遍,而且是在面试中经常被提...

zxca368
2017/09/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

RS-232、RS422和RS-485的区别和各自的实现方式

一、殊途同归 RS-232、RS422和RS-485 均属于UART是通用异步收发传输器(Universal Asynchronous Receiver/Transmitter),仅用两根信号线(Rx 和Tx)就可以完成通信过程; 而由于各自使用的电...

rainbowcode
42分钟前
0
0
spring 本类中方法调用另外一个方法事务不生效

1、在spring配置文件中添加 <aop:aspectj-autoproxy expose-proxy="true" proxy-target-class="true" />声明自动代理 <!-- 标识通过aop框架暴露该代理,aopContext能够访问. --> proxy-targe......

重城重楼
47分钟前
5
0
项目 banner 乱弹

------------------------------------------ 村上春树 ------------------------------------- 如果我爱你,而你也正巧爱我,你头发乱了的时候,我会笑笑地替你拨一拨,然后手还留恋地在你...

宿小帅
59分钟前
3
0
PHP获取未来七天的日期和星期

php获取未来七天的日期和星期代码 第一步:获取需要天数的日期,然后调用函数 //获取未来七天的日期 for($i=1;$i<8;$i++){ $dateArray[$i]=date('Y-m-d',strtotime(d...

一只懒猫-
今天
2
0
总结:IO模型

分类 多路复用 参考文章: https://www.jianshu.com/p/6a6845464770 https://www.cnblogs.com/zingp/p/6863170.html https://blog.csdn.net/sehanlingfeng/article/details/78920423......

浮躁的码农
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部