快速排序

快速排序采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。原理：
对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程。
步骤：

• 分解。将输入的序列array[m...n]划分成两个非空子序列array[m..k]和array[k+1...n]，使array[m...k]中任一元素的值不大于array[k+1...n]中任一元素的值。
• 递归求解。通过递归调用快速排序算法分别对array[m...k]和array[k+1...n]进行排序。
• 合并。由于对分解出的两个子序列的排序是就地进行的，所以在array[m...k]和array[k+1...n]都排好序后不需要执行任何计算array[m...n]就已排好序。

public static void sort(int []a, int low, int high){
    int i,j;
    int index;
    if(low >= high){
        return;
    }
    i = low;
    j = high;
    index = a[i]; //数组的第一个作为中轴基准数
    while(i < j){
        while(i < j && a[j] >= index){
            j--;
        }
        if(i<j){
            a[i++] = a[j]; //比中轴小的记录移到低端     
        }
        while(i < j && array[i] < index){
            i++;
        }
        if(i < j){
            a[j--] = a[i]; //比中轴大的记录移到高端     
        }
    }
    a[i] = index;
    sort(a,low,i-1);
    sort(a,i+1,high);
}