快速排序

1. 采用快速排序，一般可以达到O(Nlog(N)),最糟糕情况是O(N^2)。
2. 基本思想：对于排列成递增序列，每次将数组分成两半，确保左边的小于右边的，而后递归调用；递减序列相反。
3. 代码：仅供参考（代码摘自 http://www.roseindia.net/java/beginners/arrayexamples/QuickSort.shtml），加了中文注释。
public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};
    System.out.println("Quick Sort\n\n");
    System.out.println("Values Before the sort:\n");
    for(i = 0; i<array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }
  public static void quick_srt(int array[],int low, int n){
    int lo = low;
    int hi = n;
    if (lo >= n) { // 判断排序是否终止
      return;
    }
    int mid = array[(lo + hi) / 2];// 取数组中值，保证左边的都比它小，右边的都比它大
    while (lo < hi) {
      while (lo<hi && array[lo] < mid) { // 跳过已经满足的，左边小。
        lo++;
      }
      while (lo<hi && array[hi] > mid) { // 跳过已经满足的，右边大。
        hi--;
      }
      if (lo < hi) {//各自指到左右两端不符合条件的位置，交互
        int T = array[lo];
        array[lo] = array[hi];
        array[hi] = T;
      }
    }
    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
// 分别处理两个字串
    quick_srt(array, low, lo);  // 左
    quick_srt(array, lo == low ? lo+1 : lo, n); // 右
  }
}