MapReduce框架中全排序的算法思想--学习笔记
?
?关于全排序的问题? Tom White的书中提出的数据取样方法 ，最近学习了一下，下面做个比较，以防后患！！
?
?
主要思想就是在要排序的所有数据中随机取出一定量的数据，这些数据取自三个部分，
1.选取总得数据(键值对)数目
2.选取的split数目
3.每个split选取的键值对数目（只要达到总得键值对数目马上停止采集）
?
?
note ：这其中的mapClass ReducerClass都设置成默认的即可，即直接输出键值对，mapreduce框架自带有sort功能，即可满足条件。（为简单测试目的）
?
在mapreduce自带的框架内的TotalOrderPartitioner类就是通过读取这个_partition.lst，并生成对应的trie树，加快前缀匹配速度，以空间换取时间的思想，从而分配可以到对应的reduce内部，然后使用框架自带的排序功能进行局部的排序，从而达到整体的有序。我们也没有必要将这些文件进行合并，
?
它有3个基本特性：
1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3）每个节点的所有子节点包含的字符都不相同。
?
数据结构：
const int MaxKeySize = 25; //关键码最大位数
typedef struct { //关键码类型
KeyType * ch[MaxKeySize]; //关键码存放数组
int currentSize; //关键码当前位数
} KeyType;
?
下面贴下我自己实现的采样全局排序（为了简单? 没有实现trie树? 直接进行比较? 速度会有一定的影响）
自定义的InputFormat，从而在分片的时候进行采集：
?
?主函数：
??
