【问题】
对一百万个不相同的数字进行排序,要求时间复杂度O(1),空间复杂度尽可能小!
【分析】
大数据的排序问题,首选方法是“归并”,之前我也写过十亿个数的归并排序算法,且在此基础上的优化方案——大范围内归并小范围内插入排序等等,但本文有一个时间复杂度的要求,归并排序的时间复杂度是O(nlgn),因此我们尝试一种新闻排序算法——“bit排序法”。
“bit排序法”——待排序的数作为bit位的下标,当前位置的bit置为1,一轮遍历待排序数之后,打印出所有当前数值为1的数字下标。
最小的数据结构单位是byte,因此处理起来稍微麻烦了一点
【代码】
package com.hhf; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; /** * bit排序法 * @author HHF * 2015年11月17日17:12:37 * @version 1.0 只支持不同数据的排序 */ public class PhoneNumSort { private static String path = "E:/phoneNum.txt"; private static String resultPath = "E:/phoneNumResult.txt"; private int size = 1000000; public static void main(String[] args) { PhoneNumSort phoneNumSort = new PhoneNumSort(); //生成不相同的一百万个数 phoneNumSort.createNumber(phoneNumSort.size); //统计排序数大小 int bitSize = phoneNumSort.countLineSize(path); //用来保存数据--数组的下标为n,表示数据为8*(n-1)+k byte[] byteData = new byte[bitSize/8 + 1]; phoneNumSort.setByteData(byteData); } /** * 读取文件,并将文件中数值对应到byte类型的打他中去 * @param byteData */ private void setByteData(byte[] byteData){ int index = 0; int n = 0;//第几行 int k = 0;//第几位 try { BufferedReader br = new BufferedReader(new FileReader(path)); String str = br.readLine(); while(str!=null){ index = new Integer(str);//bit中的下标 n = index/8; k = index%8; //设置当前位置的值为1 byteData[n] += getAddNum(k); str = br.readLine(); } br.close(); StringBuffer content = new StringBuffer(); for(int i=byteData.length-1; i>-1; i--){ if(byteData[i]>=128){ byteData[i] -= 128; content.append(8*i + 8).append("\n"); } if(byteData[i]>=64){ byteData[i] -= 64; content.append(8*i + 7).append("\n"); } if(byteData[i]>=32){ byteData[i] -= 32; content.append(8*i + 6).append("\n"); } if(byteData[i]>=16){ byteData[i] -= 16; content.append(8*i + 5).append("\n"); } if(byteData[i]>=8){ byteData[i] -= 8; content.append(8*i + 4).append("\n"); }if(byteData[i]>=4){ byteData[i] -= 4; content.append(8*i + 3).append("\n"); } if(byteData[i]>=2){ byteData[i] -= 2; content.append(8*i + 2).append("\n"); } if(byteData[i]>=1){ content.append(8*i + 1).append("\n"); } } storeDataToFile(resultPath, content.toString().getBytes()); System.out.println(System.currentTimeMillis()+"--排序结果已经写入文件"); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } /** * 获得每个位置上对应应该要加的数值 * @param pos 位置 * @return 返回该位置对应的数 */ private int getAddNum(int pos){ if(pos>0 && pos<9){ return 1<<(pos-1); }else{ return 0; } } /** * 读取文章的行数 * @param path 文件路径 * @return size 数据量 */ private int countLineSize(String path){ int count = 0; try { BufferedReader br = new BufferedReader(new FileReader(path)); String str = br.readLine(); while(str!=null){ count++; str = br.readLine(); } br.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } System.out.println(System.currentTimeMillis()+"--待排序的数据量是"+count); return count; } /** * 生成指定数量的数据 * @param path 文件的路径 * @param size 数据数量 */ private void createNumber(int size){//还是需要先 定义InputStream输入流对象 if(size < 1){ return; } StringBuffer content = new StringBuffer(); for(int i=1; i<=size; i++){ content.append(i).append("\n"); } storeDataToFile(path, content.toString().getBytes()); System.out.println(System.currentTimeMillis()+"--文件创建结束 共生成了数据 "+size+" 条"); } /** * 将数据存储到文件中 * @param path * @param content */ private void storeDataToFile(String path, byte[] content){ File file = new File(path); if(!file.exists()){ try { file.createNewFile(); } catch (IOException e) { e.printStackTrace(); } } try { java.io.OutputStream os = new java.io.FileOutputStream(path); java.io.BufferedOutputStream bos = new java.io.BufferedOutputStream(os); bos.write(content); bos.flush();// 将缓冲区中的内容强制全部写入到文件中(不管是否已经全部写入)有点类似于下面的语句 bos.close(); os.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } }
--------相关推荐文章---------
《10亿个字符串的排序问题》http://java--hhf.iteye.com/admin/blogs/2166129
《大范围归并小范围插入排序》http://java--hhf.iteye.com/admin/blogs/2163465
相关推荐
SQL 用于各种数据库的数据类型 Microsoft Access、MySQL 和 SQL Server 所使用的数据类型和范围。 Microsoft Access 数据类型 数据类型 描述 存储 Text 用于文本或文本与数字的组合。最多 255 个字符。 ...
每个数据文件都包含相当数量的由8KB组成的页,即每页有8192bytes可用,每页都有96byte用于页头的存储,剩下的空间 才用来存储实际的数据,在页的最后是数据行偏移数组,也可以叫“页槽”数组,我们可以把一个页看做...
被格式化的数据可检查'rates'是否过高,或用于对比其它基线数据设置为识别system profile在期间如何变化。例如,计算每个事务中block changes可用如下公式: db block changes / ( user commits + user rollbacks ...
Tr13 是一个库,用于构建和使用只读紧凑(内存高效)内存中的数据结构,使用原始(字节序列, byte[] )键和值。 原始值可以自动转换为基本 JDK 类型,例如java.lang.String 。 结果trie是“原始的”,因为它们存储...
A、放置在排序数据的最后 B、放置在排序数据清单的最前 C、不被排序 D、保持原始次序 10.下列IP地址中,非法的IP地址组是____。 A、259.197.184.2与202.197.184.144 东大22春《计算机应用基础》在线平常作业2全文共...
答:JDO是java对象持久化的新的规范,为java data object的简称,也是一个用于存取某种数据仓库中的对象的标准化API。 CORBA? 答:CORBA标准是公共对象请求代理结构,用途为:用不同的程序设计语言书写,在不同的...
基本数据类型包括byte、int、char、long、float、double、boolean和short。 java.lang.String类是final类型的,因此不可以继承这个类、不能修改这个类。为了提高效率节省空间,我们应该用StringBuffer类 6、int...
基本数据类型包括byte、int、char、long、float、double、boolean和short。 java.lang.String类是final类型的,因此不可以继承这个类、不能修改这个类。为了提高效率节省空间,我们应该用StringBuffer类 3、int 和 ...
数据库文件的格式是跨平台的,你可以在32位和64位系统之间、甚至在Big-Endian和Little-Endian(译者注:这是两种不同的字节排序方式,Big-Endian是指一个word中的高位Byte是放在内存word区域的低地址处,而Little-...
则需要进行全表扫描, 以便将数据按照所定义的语言排序进行整理。 值范围: BINARY 或有效的语言定义名。 默认值: 从 NLS_LANGUAGE 中获得 nls_territory: 说明: 为以下各项指定命名约定, 包括日期和星期的编号, ...
基本数据类型包括byte、int、char、long、float、double、boolean和short。 java.lang.String类是final类型的,因此不可以继承这个类、不能修改这个类。为了提高效率节省空间,我们应该用StringBuffer类 3、int 和 ...
byte Byte short Short int Integer long Long float Float double Double 引用类型和原始类型的行为完全不同,并且它们具有不同的语义。引用类型和原始类型具有不同的特征和用法,它们包括:大小和速度...
按主机应用排序的 VBScript 版本列表和按版本排序的特性列表. VBScript 特性 VBScript 最新特性列表 未包含在 VBScript 中的 VBA 特性 VBScript 最新特性列表:未包含在 VBScript 中的应用程序编辑。 未包含在...
按主机应用排序的 VBScript 版本列表和按版本排序的特性列表. VBScript 特性 VBScript 最新特性列表 未包含在 VBScript 中的 VBA 特性 VBScript 最新特性列表:未包含在 VBScript 中的应用程序编辑。 未包含在...
按主机应用排序的 VBScript 版本列表和按版本排序的特性列表. VBScript 特性 VBScript 最新特性列表 未包含在 VBScript 中的 VBA 特性 VBScript 最新特性列表:未包含在 VBScript 中的应用程序编辑。 未包含在...
你可以找到在按字母排序的关键字列表中列出的 VBScript 语言的所有部分。如果你只想调阅某一部分,例如“对象”,那么语言的每一部分都有它自己更严密的章节。 如何查找呢?单击左边的某个标题,即显示该部分中包含...
你可以找到在按字母排序的关键字列表中列出的 VBScript 语言的所有部分。如果你只想调阅某一部分,例如“对象”,那么语言的每一部分都有它自己更严密的章节。 如何查找呢?单击左边的某个标题,即显示该部分中包含...
1.Java有那些基本数据类型,String是不是基本数据类型,他们有何区别。 2.字符串的操作: 写一个方法,实现字符串的反转,如:输入abc,输出cba 写一个方法,实现字符串的替换,如:输入bbbwlirbbb,输出...
byte[] data 文件数据 string contentType 文件内容类型 int lengthFile 文件长度 输出:string 支付宝处理结果 public static string Query_timestamp() 功能:用于防钓鱼,调用接口query_timestamp来获取...
4、请写出用于校验HTML文本框中输入的内容全部为数字的javascript代码 5、说说你用过那些ajax技术和框架,说说它们的区别 四. Java web部分 1、Tomcat的优化经验 2、HTTP请求的GET与POST方式的区别 3、解释一下...