精华内容
下载资源
问答
  • 排序:将要排序数据分到几有序的桶里,然后由桶内的数据再单独进行排序排序完,再将每桶里的数据按照顺序依次取出,最后组成的数据就是有序的了。可对数据范围比较大的数据依次划分范围桶(比较适合用于...

    线性排序:时间复杂度为 O(n)是线性的 不涉及元素之间的比较操作(但是对排序之间的数据比较苛刻)

    常见的三种:
    1.桶排序:将要排序的数据分到几个有序的桶里,然后由对桶内的数据再单独进行排序,排序完,再将每个桶里的数据按照顺序依次取出,最后组成的数据就是有序的了。可对数据范围比较大的数据依次划分范围桶(比较适合用于外部排序 内存有限不将数一次性加载到内存中 先将数据存储到外部磁盘中)

    2.计数排序:其实可以算是桶排序的一种特殊情况(再将桶的划分进行细化到 1 位)常见如:计算高考 500万考生的成绩进行排序 由于其范围是比较小的 满分是 750分 最低分是 0 分 我们可以将其划分为 751 个桶,将考生扫描一遍依次放入桶内 并进行计数,最后桶内数据依次取出 通常用于 数据量大 但数据范围比较小的情况

    3.基数排序:
    思想:如果一个数据的高位大于另一个数据,那么可以忽略地位认为这个数更大将一系列数据
    具体实现:每个按照位数进行划分 再进行每位的排序 通常用于 数据量大 位数也较长 不好进行桶位的划分
    例如:对全国手机用户手机号的排序 (位数不一致也可以进行补 0 的操作使得数据位数一致)

    展开全文
  • 1. 算法如下:根据快速排序划分的思想 (1) 递归所有数据分成[a,b)b(b,d]两区间,(b,d]区间内的数都是大于[a,b)区间内的数 (2) (b,d]重复(1)操作,直到最右边的区间数小于100。注意[a,b)区间不用划分...
     1. 算法如下:根据快速排序划分的思想 
    (1) 递归对所有数据分成[a,b)b(b,d]两个区间,(b,d]区间内的数都是大于[a,b)区间内的数 
    (2) 对(b,d]重复(1)操作,直到最右边的区间个数小于100个。注意[a,b)区间不用划分 
    (3) 返回上一个区间,并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分,分为[a2,b2)b2(b2,d2]两个区间,取(b2,d2]区间。如果个数不够,继续(3)操作,如果个数超过100的就重复1操作,直到最后右边只有100个数为止。 


    2.先取出前100个数,维护一个100个数的最小堆,遍历一遍剩余的元素,在此过程中维护堆就可以了。具体步骤如下: 
    step1:取前m个元素(例如m=100),建立一个小顶堆。保持一个小顶堆得性质的步骤,运行时间为O(lgm);建立一个小顶堆运行时间为m*O(lgm)=O(m lgm);       
    step2:顺序读取后续元素,直到结束。每次读取一个元素,如果该元素比堆顶元素小,直接丢弃 
    如果大于堆顶元素,则用该元素替换堆顶元素,然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素,因此需要维护堆的代价为(N-m)*O(lgm); 
    最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm)。 


    3.分块查找 

    先把100w个数分成100份,每份1w个数。先分别找出每1w个数里面的最大的数,然后比较。找出100个最大的数中的最大的数和最小的数,取最大数的这组的第二大的数,与最小的数比较。。。。


    1. package BigData;  
    2.   
    3. import java.io.*;  
    4. import java.util.PriorityQueue;  
    5. import java.util.Queue;  
    6.   
    7. public class FileTest {  
    8.     public FileTest() {  
    9.     }  
    10.   
    11.     public static void main(String[] args) {  
    12.         // madeData();  
    13.         sortData();  
    14.     }  
    15.   
    16.     private static void sortData() {  
    17.         FileReader fr = null;  
    18.         BufferedReader br = null;  
    19.         Queue<Integer> priorityQueue = new PriorityQueue<Integer>(100);  
    20.         try {  
    21.             fr = new FileReader("F:/add3.txt");  
    22.             br = new BufferedReader(fr);  
    23.             int temp;  
    24.             int temp1;  
    25.             String str = null;  
    26.             long begin3 = System.currentTimeMillis();  
    27.             while ((str = br.readLine()) != null) {  
    28.                 temp = Integer.valueOf(str);  
    29.                 if (priorityQueue.size() < 100) {  
    30.                     priorityQueue.add(temp);  
    31.                 } else {  
    32.                     temp1 = priorityQueue.poll();  
    33.                     if (temp1 < temp) {                        
    34.                         priorityQueue.offer(temp);  
    35.                     }else{  
    36.                         priorityQueue.offer(temp1);  
    37.                     }  
    38.                 }  
    39.                 System.out.println("FileReader执行耗时:" + priorityQueue.toString());  
    40.             }  
    41.             br.close();  
    42.             fr.close();  
    43.             long end3 = System.currentTimeMillis();  
    44.             System.out.println("FileReader执行耗时:" + (end3 - begin3) + " 豪秒");  
    45.             System.out.println("FileReader执行耗时:" + priorityQueue.toString());  
    46.         } catch (Exception e) {  
    47.             e.printStackTrace();  
    48.         } finally {  
    49.         }  
    50.     }  
    51.   
    52.     private static void madeData() {  
    53.         FileWriter fw = null;  
    54.         int count = 1000000;// 写文件行数  
    55.         try {  
    56.             fw = new FileWriter("F:/add3.txt");  
    57.             int temp = (int) (Math.random() * 1000000);  
    58.             long begin3 = System.currentTimeMillis();  
    59.             for (int i = 0; i < count; i++) {  
    60.                 temp = (int) (Math.random() * 1000000);  
    61.                 fw.write(temp + "\r\n");  
    62.             }  
    63.             fw.close();  
    64.             long end3 = System.currentTimeMillis();  
    65.             System.out.println("FileWriter执行耗时:" + (end3 - begin3) + " 豪秒");  
    66.         } catch (Exception e) {  
    67.             e.printStackTrace();  
    68.         } finally {  
    69.         }  
    70.     }  
    71. }  
    维护一个堆,然后向里面添加数据。。。


    展开全文
  • 请实现一个排序算法,对一个公司的员工(几进行排序。要求其时间复杂度为O(N).可以使用常量的辅助空间,不能超过O(N)。 其实这问题很常规,但是为什么我要写出来,主要是因为有几点是值得我们注意的,方法也...

       请实现一个排序算法,对一个公司的员工(几万)进行排序。要求其时间复杂度为O(N).可以使用常量的辅助空间,不能超过O(N)。
       其实这个问题很常规,但是为什么我要写出来,主要是因为有几点是值得我们注意的,方法也比较新颖。
       首先我们要明确一点,那就是几万人的年龄,根据鸽巢原理,若按最大年龄为100岁来算(不排除有>100的,终身荣誉主席,顾问什么的,但是这里我们假设没有100岁的,不然也太残忍了),至少有几百个人的年龄是相同的。也就是说数据的重复率相当的高。如果用快速和堆还有其他的排序,若不限制内存,最好的时间复杂度也是O(N*logN)。这里要求为O(N)所以我们就要想办法了,因为可以用常量的辅助空间,所以我们可以用空间来换取时间。
    具体实现代码如下:
    void SortAge(int *age,int length)
    {
        if(NULL==age || length<=0)
        return;
        const int oldestage=100;
        int timesOfAge[oldestage];  //辅助空间;
        for(int i=0;i<oldestage;i++)
        {
           timesOfAge[i]=0;  //初始化;
        }
        for(int i=0;i<oldestage;i++)
        {
           int age=age[i];
           if(age<=0 || age>=100)
           return ;
           timeOfAge[age]++;
        }
        int index=0;
        for(int i=0;i<oldest;i++)
           for(int j=0;j<timesOfAge[i];j++)  
           {
              age[index]=i;
    	  index++;
           }
    }
       数组timesOfAge用来统计每个年龄出现的次数。某个年龄出现了多少次,就在数组ages里设置几次该年龄,这样就相当于给数组age排序了。利用100个整数数组作为辅助空间换来了O(n)的效率。

    展开全文
  • 大话数据结构

    2018-12-14 16:02:18
    现实中,人与人之间关系就非常复杂,比如我的认识的朋友,可能他们之间也互相认识,这就不是简单的一对一、一对多的关系了,那就是我们今天要研究的主题——图。 7.2.1各种图定义 214 7.2.2图的顶点与边间关系 217...
  • 30ms),即使包含一百万或更多记录的数据集也是如此。 由于大多数交互仅涉及一维度,然后仅过滤器值进行很小的调整,因此增量过滤和减少比从头开始要快得多。 Crossfilter使用排序索引(以及一些纠结的hack)来...
  • JAVA上实例源码以及开源项目

    千次下载 热门讨论 2016-01-03 17:37:40
     Java波浪文字,一个利用Java处理字符的实例,可以设置运动方向参数,显示文本的字符数组,高速文本颜色,显示字体的 FontMetrics对象,得到Graphics实例,得到Image实例,填充颜色数组数据,初始化颜色数组。...
  • Message-Driven Bean EJB实例源代码 2目标文件 摘要:Java源码,初学实例,EJB实例 Message-Driven Bean EJB实例源代码,演示一个接收购物订单的消息驱动Bean,处理这订单同时通过e-mail的形式 //给客户发一个感谢...
  • 他的功绩是把千百万群众带入计算机的大门。 1 C语言概述 1.1 C语言的发展过程 1.2 当代最优秀的程序设计语言 1.3 C语言版本 1.4 C语言的特点 1.5 面向对象的程序设计语言 1.6 C和C++ 1.7 简单的C程序介绍 ...
  • 他的功绩是把千百万群众带入计算机的大门。 1 C语言概述 1.1 C语言的发展过程 1.2 当代最优秀的程序设计语言 1.3 C语言版本 1.4 C语言的特点 1.5 面向对象的程序设计语言 1.6 C和C++ 1.7 简单的C程序介绍 ...
  • java开源包1

    千次下载 热门讨论 2013-06-28 09:14:34
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包12

    热门讨论 2013-06-28 10:14:45
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • Java资源包01

    2016-08-31 09:16:25
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包101

    2016-07-13 10:11:08
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包11

    热门讨论 2013-06-28 10:10:38
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包2

    热门讨论 2013-06-28 09:17:39
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包3

    热门讨论 2013-06-28 09:20:52
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包6

    热门讨论 2013-06-28 09:48:32
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包5

    热门讨论 2013-06-28 09:38:46
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包10

    热门讨论 2013-06-28 10:06:40
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包4

    热门讨论 2013-06-28 09:26:54
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包8

    热门讨论 2013-06-28 09:55:26
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包9

    热门讨论 2013-06-28 09:58:55
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • java开源包7

    热门讨论 2013-06-28 09:52:16
    GWT Advanced Table 是一个基于 GWT 框架的网页表格组件,可实现分页数据显示、数据排序和过滤等功能! Google Tag Library 该标记库和 Google 有关。使用该标记库,利用 Google 为你的网站提供网站查询,并且可以...
  • 最新Java面试宝典pdf版

    热门讨论 2011-08-31 11:29:22
    18、个用户表中有个积分字段,假如数据库中有100多万个用户,若要在每年第天凌晨将积分清零,你将考虑什么,你将想什么办法解决? 107 19、个用户具有多个角色,请查询出该表中具有该用户的所有角色的其他...
  • Java面试宝典-经典

    2015-03-28 21:44:36
    18、个用户表中有个积分字段,假如数据库中有100多万个用户,若要在每年第天凌晨将积分清零,你将考虑什么,你将想什么办法解决? 107 19、个用户具有多个角色,请查询出该表中具有该用户的所有角色的其他...
  • java面试题

    2018-01-01 15:35:15
    84.8. 将一键盘输入的数字转化成中文输出(例如:输入1234567,输出:一百二拾三四千五百六拾七),请用java语言编一段程序实现! 114 84.9. 题目1:用1、2、2、3、4、5这六数字,用java写一main函数,打印出所有...
  • Apache Hive: 是基于Hadoop的一个数据仓库工具,可以将结构化的数据文件映射为一张数据库表,通过类SQL语句快速实现简单的MapReduce统计,不必开发专门的MapReduce应用,十分适合数据仓库的统计分析 笔记 Hive篇 ...
  • Java面试宝典2010版

    2011-06-27 09:48:27
    18、个用户表中有个积分字段,假如数据库中有100多万个用户,若要在每年第天凌晨将积分清零,你将考虑什么,你将想什么办法解决? 19、个用户具有多个角色,请查询出该表中具有该用户的所有角色的其他用户。...

空空如也

空空如也

1 2 3
收藏数 59
精华内容 23
关键字:

对一百万个数据进行快速排序