Quick sort

快速排序是一种分治算法，将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的：归并排序将数组分为两个数组分别排序，并将有序的数组归并以将整个数组排序；而快速排序对数组排序的方式则是当两个数组都有序时，整个数组也就自然有序了。在归并排序中，对整个数组的处理在递归调用之后，而在快速排序中，对整个数组的处理在递归调用之前。

public class Quick{
    public static void sort(Comparable[] a){
        StdRandom.shuffle(a);            //消除对输入的依赖
        sort(a,0,a.length-1);
    }
    private static void sort(Comparable[] a, int lo, int hi){
        if( hi <= lo) return;
        int j = partition(a, lo, hi);    //切分数组
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }
    private static int partition(Comparable[] a, int lo, int hi){
        int i = lo, j = hi +1;
        Comparable v = a[lo];
        while(true){
            while( less(a[++i],v) if (i == hi) break;
            while( less(v, a[--j]) if(j == lo) break;
            if( i>= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
}

快速排序递归的将子数组a[lo..hi]排序，先用partition()方法将a[j]放到一个合适的位置，然后再递归调用将其他位置的元素排序。
快速排序的最好情况是每次都正好能将数组对半分，这种情况下快速排序所用的比较次数正好能满足递归的Cn = 2Cn/2 + N的公式。 2Cn/2表示将两个子数组排序的成本，由归并排序的命题结论，这个递归公式的解为Cn~NlgN。对于更一般的情况，快速排序有以下命题：

将长度为N的无重复数组排序，快速排序平均需要~2NlgN次比较（以及1/6次交换）

• 快速排序的改进
  1.插入排序
  和大多数递归算法一样，改进快速排序性能的一个最简单的方法基于以下两点：

  • 对于小数组，快速排序比插入排序慢。
  • 因为是递归，快速排序的的sort()方法在小数组中也会调用自己。

  因此，在排序小数组时应当切换到插入排序。简单的改动即可实现这一点:
  if ( hi <= lo+ M ) { Insertion.sort(a, lo, hi); return }
  //原语句为if(hi <= lo) return;
  转换参数M的最佳值与系统有关，但是5 ~ 15之间的任意值在大多数情况下都能令人满意。
  2.三取样切分
  改进快速排序性能的第二个方法是使用子数组的一小部分元素的中位数来切分数组。人们发现将取样设为3并用大小居中的元素切分效果最好。
  3.熵最优排序
  实际运用中常常会有大量重复元素的数组，而此时快速排序有巨大的提升空间，例如一个所有元素都相等的子数组就不需要再排序了，但我们的算法还会继续将它们切分到更小的数组。一个简单的改进方法是将数组切分为三部分，分别对应与小于，等于和大于切分数组的元素。从左到右遍历数组一次，维护一个指针lt使得a[lo..lt-1]中的元素都小于v，一个指针gt使得a[gt+1..hi]中的元素都大于v，一个指针i使得a[lt..i-1]中的元素都等于v。
  public class Quick3way{
  private static void sort(Comparable[] a, int lo, int hi){
  if( hi <= lo ) return;
  int lt = lo, i = lo+1, gt = hi;
  Comparable v = a[lo];
  while(i <= gt){
  int cmp = a[i].CompareTo(v);
  if (cmp < 0) exch(a, lt++, i++);
  else if( cmp > 0) exch(a, i, gt--);
  else i++;
  }
  sort(a, lo, lt-1);
  sort(a, gt+1, hi);
  }
  }