题目大意：移动公司需要对已经发放的所有139段的号码进行统计排序，已经发放的139号码段的文件都存放在一个文本文件中（原题是放在两个文件中），一个号码一行，现在需要将文件里的所有号码进行排序，并写入到一个新的文件中；号码可能会有很多，最多可能有一亿个不同的号码（所有的139段号码），存入文本文件中大概要占1.2G的空间；jvm最大的内存在300以内，程序要考虑程序的可执行性及效率；只能使用Java标准库，不得使用第三方工具。
这是个典型的大数据量的排序算法问题，首先要考虑空间问题，一下把1.2G的数据读入内存是不太可能的，就算把1一亿条数据，转都转换成int类型存储也要占接近400M的空间。当时做个题目我并没有想太多的执行效率问题，主要就考虑了空间，而且习惯性的想到合并排序，基本思想是原文件分割成若干个小文件并排序，再将排序好的小文件合并得到最后结果，算法大概如下：
1.顺序读取存放号码文件的中所有号码，并取139之后的八位转换为int类型；每读取号码数满一百万个（这个数据可配置）将已经读取的号码排序并存入新建的临时文件。
2.将所有生成的号码有序的临时文件合并存入结果文件。
这个算法虽然解决了空间问题，但是运行效率极低，由于IO读写操作太多，加上步骤1中的排序的算法（快速排序）本来效率就不高（对于电话排序这种特殊情况来说），导致1亿条数据排序运行3个小时才有结果。
如果和能够减少排序的时间呢？首当其冲的减少IO操作，另外如果能够有更加好排序算法也行。前天无聊再看这个题目时突然想到大三时看《编程珠玑》时上面也有个问题的需求这个这个题目差不多，记得好像使用是位向量（实际上就是一个bit数组），用电话作为index，心中大喜，找到了解决此问题的最完美方案啦：用位向量存储电话号码，一个号码占一个bit，一亿个电话号码也只需要大概12M的空间；算法大概如下：
1.初始化bits[capacity]；
2.顺序所有读入电话号码，并转换为int类型，修改位向量值：bits[phoneNum]=1；
3.遍历bits数组，如果bits[index]=1，转换index为电话号码输出。
Java中没有bit类型，一个boolean值占空间为1byte（感兴趣的可以自己写程序验证），我自己写个个用int模拟bit数组的类，代码如下：
public class BitArray {
private int[] bits = null;
private int length;
//用于设置或者提取int类型的数据的某一位(bit)的值时使用
private final static int[] bitValue = {
0x80000000,//10000000 00000000 00000000 00000000
0x40000000,//01000000 00000000 00000000 00000000
0x20000000,//00100000 00000000 00000000 00000000
0x10000000,//00010000 00000000 00000000 00000000
0x08000000,//00001000 00000000 00000000 00000000
0x04000000,//00000100 00000000 00000000 00000000
0x02000000,//00000010 00000000 00000000 00000000
0x01000000,//00000001 00000000 00000000 00000000
0x00800000,//00000000 10000000 00000000 00000000
0x00400000,//00000000 01000000 00000000 00000000
0x00200000,//00000000 00100000 00000000 00000000
0x00100000,//00000000 00010000 00000000 00000000
0x00080000,//00000000 00001000 00000000 00000000
0x00040000,//00000000 00000100 00000000 00000000
0x00020000,//00000000 00000010 00000000 00000000
0x00010000,//00000000 00000001 00000000 00000000
0x00008000,//00000000 00000000 10000000 00000000
0x00004000,//00000000 00000000 01000000 00000000
0x00002000,//00000000 00000000 00100000 00000000
0x00001000,//00000000 00000000 00010000 00000000
0x00000800,//00000000 00000000 00001000 00000000
0x00000400,//00000000 00000000 00000100 00000000
0x00000200,//00000000 00000000 00000010 00000000
0x00000100,//00000000 00000000 00000001 00000000
0x00000080,//00000000 00000000 00000000 10000000
0x00000040,//00000000 00000000 00000000 01000000
0x00000020,//00000000 00000000 00000000 00100000
0x00000010,//00000000 00000000 00000000 00010000
0x00000008,//00000000 00000000 00000000 00001000
0x00000004,//00000000 00000000 00000000 00000100
0x00000002,//00000000 00000000 00000000 00000010
0x00000001 //00000000 00000000 00000000 00000001
};
public BitArray(int length) {
if(length < 0){
throw new IllegalArgumentException("length必须大于零！");
}
bits = new int[length / 32 + (length % 32 > 0 ? 1 : 0)];
this.length = length;
}
//取index位的值
public int getBit(int index){
if(index <0 || index > length){
throw new IllegalArgumentException("length必须大于零小于" + length);
}
int intData = bits[index/32];
return (intData & bitValue[index%32]) >>> (32 - index%32 -1);
}
//设置index位的值，只能为0或者1
public void setBit(int index,int value){
if(index <0 || index > length){
throw new IllegalArgumentException("length必须大于零小于" + length);
}
if(value!=1&&value!=0){
throw new IllegalArgumentException("value必须为0或者1");
}
int intData = bits[index/32];
if(value == 1){
bits[index/32] = intData | bitValue[index%32];
}else{
bits[index/32] = intData & ~bitValue[index%32];
}
}
public int getLength(){
return length;
}
}
bit数组有了，剩下就是算法代码，核心代码如下：
bitArray = new BitArray(100000000);
//顺序读取所有的手机号码
while((phoneNum = bufferedReader.readLine())!=null){
phoneNum = phoneNum.trim().substring(3);//13573228432
//取139后8位转换为int类型
phoneNumAsInt = Integer.valueOf(phoneNum);
//设置对应bit值为1
bitArray.setBit(phoneNumAsInt, 1);
}
//遍历bit数组输出所有存在的号码
for(int i = 0;i<sortUnit;i++){
if(bitArray.getBit(i)==1){
writer.write("139" + leftPad(String.valueOf(i + sortUnit*times), 8));
writer.newLine();
}
}
writer.flush();
经测试，修改后的算法排序时只需要20多M的内存，一亿条电话号码排序只要10分钟（时间主要花在IO上），看来效果还是很明显的。
这个算法很快，不过也有他的局限性：
1.只能用于整数的排序，或者可以准确映射到正整数（对象不同对应的正整数也不相同）的数据的排序。
2.不能处理重复的数据，重复的数据排序后只有一条（如果有这种需求可以在这个算法的基础上修改，
给出现次数大于1的数据添加个计数器，然后存入Map中）
3.对于数据量极其大的数据处理可能还是比较占用空间，
这种情况可配合多通道排序算法解决。
PS:这个算法的思想源于《编程珠玑》，有兴趣的可以读读那本书，非常不错！
分享到：
相关推荐
例如，排序算法中的快速排序、归并排序可以被并行化；图算法如Floyd-Warshall短路径算法、BFS（广度优先搜索）和DFS（深度优先搜索）也可以在并行计算中优化。此外，还有并行计算的经典问题，如矩阵乘法、大整数乘法...
这份“中科大算法设计与分析复习重点.zip”压缩包文件正是为准备这门课程考试的学生量身定制的复习材料。 复习重点通常会涵盖以下几个关键知识点： 1. **基本概念**：了解什么是算法，它的特性，以及如何用伪代码...
考试通常包含一道编程题，主要考核C语言的基础概念，如： - **循环语句**：for、while、do...while等，以及如何正确控制循环流程。 - **分支语句**：if...else、switch...case等，用于逻辑判断和执行不同代码路径。 ...
- **外部排序**：针对大数据量的排序算法，如多路归并排序等。 以上是根据提供的文件信息整理出的主要知识点，这些知识点对于准备《数据结构》考研的学生来说至关重要。通过深入理解和掌握这些知识点，可以帮助考生...
程序排序算法分析 - 给定的程序片段展示了一个简单的选择排序算法。经过排序后，数组中的元素位置发生了变化，最终输出的结果为 `1,2,7,6,5,4,3,8,9,10`。 ### 8. 数据库基础知识 - **数据处理**：是将原始数据...
时间复杂度用来描述算法执行时间与输入数据量之间的关系。题目中的代码片段展示了一个while循环，其中变量`x`从2开始，每次乘以2，直到`x >= n/2`为止。这种情况下，循环的次数取决于`n`的大小，实际上是对数增长的...
### 计算机二级等级考试知识点解析 #### 题目1: 数据处理与表的创建 - **知识点概述**: - 在本题中，考生需要了解在数据库操作中，如何通过不同的命令来创建新的表。 - `COPY TO` 命令用于根据指定条件复制记录到...
根据给定文件的信息，我们可以从中提炼出多个计算机科学领域的知识点，包括...通过上述分析，我们可以看到这份试题覆盖了计算机科学领域中的多个核心知识点，从数据结构、算法到计算机组成原理等多个方面进行了考查。
题目描述了一种排序方法，并要求识别这是哪种排序算法。 **解析**：题目描述的方法是在排序过程中，每次将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置。这种排序方法被称为插入排序。因此，...
本题是来自2006-2007年度北美地区ACM国际大学生程序设计竞赛的一道题目，题目编号为3746，题目名为“过敏的机器人”（Allergic Robot）。该题目的主要背景设定在一种特殊的场景下：一个能够帮助人们从传送带上挑选所...
- **应用**: 大整数加减乘除。 #### 三、ACM竞赛题型分析 - **动态规划**: 适用于状态转移清晰的问题。 - **贪心算法**: 适合能分解成多个子问题的优化问题。 - **穷举搜索**: 对于规模较小的问题适用。 - **最短...
- **题目解析**：题目提供了一组数据的排序过程，要求根据排序过程判断使用的排序算法。 - **选项分析**： - A选项“堆排序”不符合题目的排序过程。 - B选项“冒泡排序”也不符合题目的排序过程。 - C选项...
Java蓝桥杯作为一项著名的计算机编程竞赛，主要面向高校学生，旨在通过解决一系列富有挑战性的编程题目来提升参赛者的程序设计和算法分析能力。在这篇文章中，我们将详细解析几类典型的Java蓝桥杯试题，并对解题过程...
### 信息学奥赛2023年NOIP真题分析——词典 #### 题目背景 信息学奥林匹克联赛（CCF NOIP）是中国计算机学会主办的一项面向全国青少年的信息学竞赛活动，旨在选拔优秀的信息学人才。2023年的NOIP真题包含了四道编程...
- **应用场景**：掌握二叉树的遍历算法是理解和实现树相关数据结构的关键，特别是在构建高效的搜索和排序算法时。 7. **十进制数与四进制数的转换** - **知识点**：十进制数转换为四进制数的方法是不断除以4并...
本题考查了应聘者对于排序算法的理解和应用，同时也考察了应聘者对于问题的分析和抽象能力。通过排序优化复习策略，可以有效地减少计算量，提高解决问题的效率。此外，题目还涉及到了基本的数据结构操作和条件判断，...