1 一亿数据取最大前10000个

采用最小堆法，首先读入前 10000 个数来创建大小为 10000 的最小堆，建堆的时间复 杂度为 O(mlogm)(m 为数组的大小即为 10000)，然后遍历后续的数字，并于堆顶(最小)数字进行比较。如果比最小的数小，则继续读取后续数字;如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有 10000 个数字。该算法的时间复杂度为 O (nmlogm)，空间复杂度是 10000(常数)。

2 一百亿数据排序

假设为int型，则：

100亿数字 = 4 * 100 0000 0000 B = 4 * 9765625K（约等于400 0000 0 K） = 4 * 9536M（约等于40000M） = 37.25G（约等于40G）

1.把这个37GB的大文件，用哈希分成1000个小文件，每个小文件平均37MB左右（理想情况），把100亿个数字对1000取模，模出来的结果在0到999之间，每个结果对应一个文件，所以我这里取的哈希函数是 h = x % 1000，哈希函数取得”好”，能使冲突减小，结果分布均匀。

2.拆分完了之后，得到一些几十MB的小文件，那么就可以放进内存里排序了，可以用快速排序，归并排序，堆排序等等。

3.1000个小文件内部排好序之后，就要把这些内部有序的小文件，合并成一个大的文件，可以用二叉堆来做1000路合并的操作，每个小文件是一路，合并后的大文件仍然有序。

首先遍历1000个文件，每个文件里面取第一个数字，组成 (数字, 文件号) 这样的组合加入到堆里（假设是从小到大排序，用小顶堆），遍历完后堆里有1000个 (数字，文件号) 这样的元素

然后不断从堆顶拿元素出来，每拿出一个元素，把它的文件号读取出来，然后去对应的文件里，加一个元素进入堆，直到那个文件被读取完。拿出来的元素当然追加到最终结果的文件里。

按照上面的操作，直到堆被取空了，此时最终结果文件里的全部数字就是有序的了。

3 链表反转

 public static void main(String[]args){
        Node node3=new Node(3,null);
        Node node2=new Node(2,node3);
        Node node1=new Node(1,node2);
        reverse(node1);
        Node current=node3;
        while(current!=null){
        System.out.println(current.getCurrentId());
        current=current.getNext();
        }
        }

public static void reverse(Node head){
        Node current=head;
        Node prev=null;
        Node next=null;
        while(current!=null){
        next=current.getNext();
        current.setNext(prev);
        prev=current;
        current=next;
        }
        }

public class Node {
  private Node next;
  private Integer currentId;

  public Node(Integer currentId, Node next) {
    this.next = next;
    this.currentId currentId;
  }

  public Node getNext() {
    return this.next;
  }

  public void setNext(Node next) {
    this.next = next;
  }
}