Comparable 和Comparator的区别

Comparable是排序接口；若一个类实现了Comparable接口，就意味着“该类支持排序”。

而Comparator是比较器接口；我们若需要控制某个类的次序，可以新建一个“该类的比较器”来进行排序。

我们不难发现：Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

下面两个例子是对Node的count值进行比较

Comparable写法
class Node implements Comparable<Node>{
    int num;
    int count;
    public Node(int num){
        this.count = 0;
        this.num = num;
    }
    @Override
    public int compareTo(Node o){
        return this.count - o.count;
    }
}

Comparator写法
 private Comparator<Node> cmp = new Comparator<Node>(){
        public int compare(Node a, Node b){
            return a.count - b.count;
        }
    };

quicksort手动实现

   参考 http://w4lle.github.io/2016/07/03/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/
http://www.jianshu.com/p/a0c93033f8ba

http://flyingcat2013.blog.51cto.com/7061638/1281614

挖坑大法

     public static void quickSort(int[] arr){
      qsort(arr, 0, arr.length-1);
}


private static void qsort(int[] arr, int l, int r){
 int left = l;
 int right = r;
 int key;
 if(l < r){   //必须的
  key = arr[l];//最左挖坑
  while(l<r){
  while(r> l && arr[r] >= key)
  r--;
  arr[l]=arr[r];填左坑挖右坑
  while(r> l && arr[l] < key)
  l++;
  arr[r]=arr[l];填右坑挖左坑
  }
   arr[l]=key;//把左坑填回去
   qsort(arr, left, r-1 );  //partition
   qsort(arr,r+1, right);
 }
    }