大数据算法：对5亿数据进行排序
0.前言：在大数据研究的路上，我们总要对一些很大的数据进行各种各样的操作。比如说对数据排序，比如说对数据统计，比如说对数据计算。而在大量的数据面前，我们总是束手无策，因为我们无法在限定时间的情况下，在效率上做到让人满意，也无法在限定空间的情况下，能够快速解决问题。可能我们在一些日常的开发过程中，没有遇到过这些问题。不过，现在是时候来考虑一下这样的问题了。因为，现在正值大数据的时代。
在本文中我会用三种方法，从两个方面来说明如何解决对5亿数据进行排序工作。
1.版本说明商业转载请联系作者获得授权，非商业转载请注明出处。本文作者：Q-WHai发表日期：2015年10月24日本文链接：https://blog.csdn.net/lemon_tree12138/article/details/48783535来源：CSDN更多内容：分类>>算法与数学
2.思路分析：拿到这样的一个问题，你的第一感觉是什么？冒泡排序？选择排序？插入排序？堆排？还是快排？可能你的想法是我的内存不够。的确，这么大的一个数据量，我们的内存的确不够。因为单是5亿的整数数据就有3.7个G(别说你是壕，内存大着呢)。既然内存不够，那么我们要怎么来解决呢？
要知道我们一步做不了的事，两步总能做到。那么我们就来尝试第一步做一些，剩下的一些就等会再来搞定吧。基于这样的思路，就有下面的一个解题方法——分治！
1.分治——根据数据存在文件中的位置分裂文件到批量小文件中
相对于朴素的排序，这是一种比较稳妥的解决方法。因为数据量太大了！我们不得不将大事化小，小事化了。
这里我们的做法是每次读取待排序文件的10000个数据，把这10000个数据进行快速排序，再写到一个小文件bigdata.part.i.sorted中。这样我们就得到了50000个已排序好的小文件了。
在有已排序小文件的基础上，我只要每次拿到这些文件中当前位置的最小值就OK了。再把这些值依次写入bigdata.sorted中。
2.分治——根据数据自身大小分裂文件到批量小文件中
按照数据位置进行分裂大文件也可以。不过这样就导致了一个问题，在把小文件合并成大文件的时候并不那么高效。那么，这里我们就有了另一种思路：我们先把文件中的数据按照大小把到不同的文件中。再对这些不同的文件进行排序。这样我们可以直接按文件的字典序输出即可。
3.字典树
关于字典树的基本使用，大家可以参见本人的另一篇博客：《数据结构：字典树的基本使用》
基于《数据结构：字典树的基本使用》这篇博客中对字典序的讲解，我们知道我们要做就是对字典树进行广度优先搜索。
3.结构设计图：
4.代码分析：0.分治(0)分割大文件
此步对大文件的分割是按序进行的，这样我们就可以确保数据的离散化，不会让一个小文件中的数据很多，一个小文件的数据很少。
publicstaticvoidsplitBigFile2PartBySerial(StringfilePath,StringpartPath)throwsIOException{Filefile=newFile(filePath);FileInputStreaminputStream=newFileInputStream(file);BufferedReaderreader=newBufferedReader(newInputStreamReader(inputStream));StringBufferbuffer=newStringBuffer();StringreaderLine="";intline=0;while((readerLine=reader.readLine())!=null){buffer.append(readerLine+"");if(++line%Config.PART_NUMBER_COUNT==0){sortStringBuffer(buffer);intsplitLine=line/Config.PART_NUMBER_COUNT;write(partPath.replace("xxx",""+splitLine),buffer.toString());buffer.setLength(0);System.out.println("SPLIT:"+splitLine);}}reader.close();}
(1)排序
即使是已经切割成小份的了，不过每个小文件中的数据集仍然有50000个。因为50000个数据也不是一个小数据，在排序的过程中，也会有一些讲究，所有这里我们使用的是快排。如下：
publicstaticvoidsortStringBuffer(StringBufferbuffer){String[]numberTexts=buffer.toString().split("");buffer.setLength(0);int[]numbers=newint[numberTexts.length];for(inti=0;i