快速排序

平均T=O(nlogn) 最坏Tmax=O(n^2)

基本思想：

简记：

　以最左端元素为分划元素（主元），然后
　左找大，右找小；
　调换后继续找；
　越界后停止查找和调换。最后，
　调位主元和l[j]，再在主元前后继续分划。 　　

代码：

public class QuickSortTest {    
    /**
     * 分划函数
     *   将下标在[left,right]范围内的序列，以主元l[left]为中心
     *   分划成左右两个子序列，最后返回分划点j。
     */
    private static int Partition(int[] l, int left, int right){
        //前置条件：left<=right
        int i=left, j=right+1; //哨兵位（防止越界）
        do{
            //'i++'即表示已将主元l[left]排除在外
            do i++; while(l[i]<l[left]&&left<right); //从首端（left+1起）向后找到>=主元的元素时停止；这里需要手动添加循环终止条件：left<right，当left=right时停止循环，否则它不会自己停下来，造成角标越界。
            do j--; while(l[j]>l[left]); //从末端（right起）向前找到<=主元的元素时停止；或当自减的j=left时，l[j]=主元自动停止循环。

            if(i<j) Swap(l, i, j); //若大元素在小元素的前面则调换二者位置
        }while(i<j); //若未越界则继续查找和调换

        Swap(l, left, j); //调换l[left]和l[j]
        return j; 
    }
    /** 调换两个元素的位置 **/
    private static void Swap(int[] l, int i, int j) {
        int temp = l[i];
        l[i] = l[j];
        l[j] = temp;
    }


    public static void QuickSort(int[] l){ //缺省参数：则排序所有元素
        QuickSort(l, 0, l.length-1);
    }

    //重载：对l[left~right]范围内的元素进行排序
    public static void QuickSort(int[] l, int left, int right){
        if(left<right){ //当序列长度大于1时，则进行分划（此处也避免了Partition函数向右划分到末端时的角标越界，当left=right=l.length-1时自动跳出循环）
            int j = Partition(l, left, right); //对[left,right]范围内的序列进行分割
            QuickSort(l, left, j-1); //对左子序列实施快排
            QuickSort(l, j+1, right); //对右子序列实施快排

            //每分划一次则确定一个元素位置；分划完成即排序完成
            //递归总次数：log2^(l.length)
        }
    }
}

另一种写法：
　　（基本思想是一样的，只是将主元从arr[left]换成了arr[right]，且分划函数Partition的主循环也从三个do-while循环换成了三个while循环）

public class quickSortTest {

    private static void recQuickSort(int arr[], int left, int right) {
        if (right - left <= 0) {
            return;
        } else {
            int pivot = arr[right]; //一般使用数组最右边的元素作为枢纽
            int partition = partitionIt(arr, left, right, pivot);
            recQuickSort(arr, left, partition - 1);
            recQuickSort(arr, partition + 1, right);
        }
    }

    /** 
     *  划分：
     *     划分是快速排序的根本机制，划分本身也是一个有用的操作。
     *     划分数据就是把数据分为两组，使所有关键字大于特定值的数据项在一组，所有关键字小于特定值的数据项在另一组。
     */
    private static int partitionIt(int[] arr, int left, int right, int pivot) {
        int leftPtr = left-1;
        int rightPtr = right; //使用最右边的元素作为主元枢纽，划分时就要将最右端的数据项排除在外
        while (true) {
            while (arr[++leftPtr] < pivot); //从前往后找到不比arr[right]小的元素时停止；或当自增的leftPtr=right时，arr[leftPtr]=pivot=arr[right]会自动停止循环
            while (rightPtr > 0 && arr[--rightPtr] > pivot); //从后往前找不比arr[right]大的元素时停止；这个需要手动添加循环终止条件rightPtr>0以防角标越界。

            if (leftPtr >= rightPtr) {
                break;
            } else {
                // 交换leftPtr和rightPtr位置的元素
                int temp = arr[leftPtr];
                arr[leftPtr] = arr[rightPtr];
                arr[rightPtr] = temp;
            }
        }
        // 交换leftPtr和right位置的元素
        int temp = arr[leftPtr];
        arr[leftPtr] = arr[right];
        arr[right] = temp;
        return leftPtr;// 返回枢纽位置
    }
}