快速排序

快速排序的基本思想：通过一趟排序将待排记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的任意关键字小，则可分别对这两部分继续排序，已达到整个序列有序的目的。

以下为该算法的主体

public static void quickSort(int[] arr, int low, int high){
    int povit;
    if(high > low){
        povit = partition(arr, low, high);
        quickSort(arr, low, povit - 1);
        quickSort(arr, povit + 1, high);
    }
}

不过，快排算法的核心是partition方法。

值得注意的是，povit索引对应的值并没有将序列分为等长的两个子序列，两个子序列的长度对于程序员往往是随机的。一般取序列中的第一个元素作为povitKey，从而将序列一分为二。要将povitKey移到相应的位置，可以用low、high两个指针，往两头向内缩小范围直至找到povitKey最后的位置，并且low左边的元素均小于high右边的元素。

public static int partition(int[] arr, int low, int high){
    int povitKey = arr[low];
    while(high > low){
        while(high > low && arr[high] >= povitKey)
            high --;
        swap(arr, low, high);
        while(high > low && arr[low] <= povitKey)
            low ++;
        swap(arr, low, high);
    }
    return low;
}
pulic static void swap(int[] arr, int low, int high){
    int temp = arr[low];
    arr[low] = arr[low];
    arr[high] = temp;
}