海量数据的排序和查找

位图法
使用场景举例：对2G的数据量进行排序，这是基本要求。
数据：1、每个数据不大于8亿；2、数据类型位int；3、每个数据最多重复一次。
内存：最多用200M的内存进行操作。
首先对占用的内存进行判断，每个数据不大于8亿，那么8亿是一个什么概念呢。
1 byte = 8 bit（位）
1024 byte = 81024 bit = 1k
1024 k = 81024*1024 bit = 1M = 8388608 bit
也就是1M=8388608位
而位图法的基本思想就是利用一位代表一个数字，例如3位上为1,则说明3在数据中出现过，若为0，则说明3在数据中没有出现过。所以当题目中出现每个数据最多重复一次这个条件时，我们可以考虑使用位图法来进行大数据排序。比如说有一个同等长度的int数组，原来一个int元素用来表示一个数据，现在利用int元素的每一位，它可以表示32个元素。
那么假如使用位图法来进行这题的排序，内存占用多少呢。由题目知道每个数据不大于8亿，那么我们就需要8亿位，占用800000000/8388608=95M的空间，满足最多使用200M内存进行操作的条件，这也是这题能够使用位图法来解决的一个基础。
关键代码：

建立一个足够大的Bit数组当做hash表，以bit数组的下标来表示一个整数，以bit位中的0或1来表示这个整数是否在这个数组中存在，适用于无重复原始数据的搜索，原来的每个整数需要4byte空间变为1Bit,空间压缩率为32倍。
堆排序法
堆排序是4种平均时间复杂度为nlogn的排序方法之一，其优点在于当求M个数中的前n个最大数，和最小数的时候性能极好。所以当从海量数据中要找出前m个最大值或最小值，而对其他值没有要求时，使用堆排序法效果很好。
使用场景：从1亿个整数里找出100个最大的数
步骤：
1.读取前100个数字，建立最大值堆。（这里采用堆排序将空间复杂度讲得很低，要排序1亿个数，但一次性只需读取100个数字，或者设置其他基数，不需要1次性读完所有数据，降低对内存要求）
2、依次读取余下的数，与最大值堆作比较，维持最大值堆。可以每次读取的数量为一个磁盘页面，将每个页面的数据依次进堆比较，这样节省IO时间。
3.将堆进行排序，即可得到100个有序最大。
这里再补充学习一下堆排序
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
https://www.cnblogs.com/chengxiao/p/6129630.html（记得看这篇微博，讲得很好~~~~）
分治策略
分治法的核心就是将一个复杂的问题通过分解抽象成若干个简单的问题。
应用场景：10G的数据，在2G内存的单台机器上排序的算法
我的想法，这个场景既没有介绍数据是否有重复，也没有给出数据的范围，也不是求最大的个数。而通过分治虽然可能需要的io次数很多，但是对解决这个问题还是具有一定的可行性的。
步骤：
1、从大数据中抽取样本，将需要排序的数据切分为多个样本数大致相等的区间，例如：1-100，101-300…
2、将大数据文件切分为多个小数据文件，这里要考虑IO次数和硬件资源问题，例如可将小数据文件数设定为1G（要预留内存给执行时的程序使用）
3、使用最优的算法对小数据文件的数据进行排序，将排序结果按照步骤1划分的区间进行存储
4、对各个数据区间内的排序结果文件进行处理，最终每个区间得到一个排序结果的文件
5、将各个区间的排序结果合并.
通过分治将大数据变成小数据进行处理，再合并。
分治的步骤可以采取快排等等。。。。。
希望自己利用碎片时间，多多学习这些基础部分的东西，充实自己，加油！！！