今天面试问了一道10万条数据的手机号码如何排序问题，请前辈讨论一下。。

Question

放到list里让他自己排？
不知道效率如何

Answer 1

关注...我的思路是把这些数据分成n份来处理,比如10份,那一份1万条数据,用个long数组来排序,一万条数据也就80kb左右吧这些数据分别排序,然后多路归并  写到要求的文件中 

Answer 2

发表于：2007-11-29 15:22:198楼 得分:0 
放到list里让他自己排？ 
不知道效率如何 
--------------------------------------------嘿嘿，这个好不过HR一定不爽 
 

Answer 3

试了下 个人感觉10w条记录不用什么复杂的算法了 杀鸡焉用牛刀 化繁为简
直接用Collection.sort() 
This algorithm offers guaranteed n log(n) performance.
耗时一秒左右
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;public class Test { public static void main(String[] args) {
Test test = new Test();
List<String> outputList = new ArrayList<String>();
long output = 13114345369L;

System.out.println("now start");

for (int i = 0; i < 100000; i++) {
outputList.add(String.valueOf(output));
output--;
}
        System.out.println("processing");
test.outputDataToFile(outputList, "data.txt");
long startTime=System.currentTimeMillis();
test.outputDataToFile(test.readSortAndReturnList(), "outcome.txt");
System.out.println("mission complete");
long endTime=System.currentTimeMillis();
System.out.println("Total cost: "+(endTime-startTime)+" milliseconds");
} public void outputDataToFile(List outputList, String outputFileName) {
try {
OutputStreamWriter osw = new OutputStreamWriter(
new FileOutputStream(new File(outputFileName)));
for (int i = 0; i < outputList.size(); i++) { try {
osw.write(outputList.get(i).toString());
osw.write("\r\n");
} catch (IOException e) {
e.printStackTrace();
}
}
osw.flush();
osw.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
} public List readSortAndReturnList() {
List<String> list = new ArrayList<String>();
String singleLineString = null;
try {
BufferedReader br = new BufferedReader(new FileReader("data.txt"));
do {
singleLineString = br.readLine();
if (singleLineString != null) {
list.add(singleLineString);
}
} while (singleLineString != null);
Collections.sort(list);
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} return list;
}
}/*
now start
processing
mission complete
Total cost: 981 milliseconds
*/

Answer 4

的确看对环境的要求，至于我说得“外排，多路归并+败者树”任何一本数据结构树上都有
java自身的sort方法应该实现是rb tree