import java.util.Arrays;

public class quickSort {
    public static void quickSort(int arr[],int startIndex,int endIndex){
        //遞歸結束條件為startIndex大于或等于endIndex
        if(startIndex>=endIndex){
            return;
        }

        //得到基準元素位置
        int pIndex=partition(arr,startIndex,endIndex);

        //根據(jù)基準元素分兩部分進行遞歸排序
        quickSort(arr,startIndex,pIndex-1);
        quickSort(arr,pIndex+1,endIndex);
    }
    /*
    * 分治法（雙邊循環(huán)法）
    * arr  待排序數(shù)組
    * startIndex  起始下標
    * endIndex  結束下標
    * */
    public static int partition(int arr[],int startIndex,int endIndex)
    {
        int p=arr[startIndex];//基準元素(可取隨機位置)
        int l=startIndex;//左指針
        int r=endIndex;//右指針

        while(l!=r){
            //控制右指針向左移動，找到小于基準元素的那個數(shù)
            while((l<r)&&(arr[r]>p)){
                r--;
            }
            //控制左指針向右移動，找到大于基準元素的那個數(shù)
            while((l<r)&&(arr[l]<=p)){
                l++;
            }
            //交換l指針和r指針所指的元素
            if(l<r){
                int tmp=arr[l];
                arr[l]=arr[r];
                arr[r]=tmp;
            }
        }

        //交換基準元素和重合點的元素
        arr[startIndex]=arr[l];
        arr[l]=p;
        return l;
    }

    public static void main(String[] args) {
        int arr[]={4,7,6,5,3,2,8,1};
        quickSort(arr,0,7);
        System.out.println(Arrays.toString(arr));
    }
}

/*
     * 分治法（單邊循環(huán)法）
     * arr  待排序數(shù)組
     * startIndex  起始下標
     * endIndex  結束下標
     * */
    public static int partition(int arr[],int startIndex,int endIndex)
    {
        int p=arr[startIndex];//基準元素(可取隨機位置)
        int mark=startIndex;

        for(int i=startIndex+1;i<=endIndex;i++){
            if(arr[i]<arr[mark]){
                mark++;
                int tmp=arr[mark];
                arr[mark]=arr[i];
                arr[i]=tmp;
            }
        }

        //交換基準元素和mark指針的元素
        arr[startIndex]=arr[mark];
        arr[mark]=p;
        return mark;
    }

    private static int minThree(int[]array,int left,int right) {
        //三數(shù)取中法，優(yōu)化遞歸實現(xiàn)的快速排序
        //使得最壞情況時，快速排序變?yōu)槎植檎?
        int mid = (left+right)/2;
        if(array[right] > array[left]) {
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
        if(array[mid] > array[left]) {
            return left;
        }
        if(array[mid] > array[right]) {
            return mid;
        }
        return right;
    }

public class QuickSort {
    /**
     * 快速排序
     * 時間復雜度：代碼未優(yōu)化時：最好情況（滿二叉樹或完全二叉樹）：O(n*logn)，    最壞情況(順序和逆序時)：O（n^2）
     * 空間復雜度：代碼未優(yōu)化時：最好情況（滿二叉樹或完全二叉樹）：O（logn），    最壞情況(順序和逆序時)：O（n）
     * 穩(wěn)定性：不穩(wěn)定
     * @param array
     */

    public static void quickSort(int[] array) {
        quick(array,0, array.length-1);
    }
    private static void quick(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }
        // 設置數(shù)量閘口，
        // 數(shù)量小，使用直接插入排序
        if(right - left + 1 < 14) {
            InsertSort(array);
            return;
        }
        
        // 將三數(shù)取中法取得的中間值換到left處
        swap(array,minThree(array,left,right),left);
        int piovt = partition(array,left,right);

        quick(array, left, piovt-1);
        quick(array,piovt+1,right);
    }

    //挖坑法
    private static int partition(int[] array,int left,int right) {
        // 在left下標挖一個坑
        int tmp = array[left];
        while (left < right) {
            // 讓right下標去找比tmp小的數(shù)
            while (right > left && array[right] >= tmp) {
                right--;
            }
            // 填left下標的坑，此時right下標變成一個坑了
            array[left] = array[right];
            // 讓left下標去找比tmp大的數(shù)
            while (left < right && array[left] <= tmp) {
                left++;
            }
            // 填right下標的坑，此時left下標變成一個坑了
            array[right] = array[left];
        }
        // 將基準值放到合適的位置
        array[left] = tmp;
        // 返回基準下標
        return left;
    }

    //Hoare法
    private static int partition3(int[] array,int left,int right) {
        // 基準值
        int tmp = array[left];
        // 基準下標
        int index = left;
        while (left < right) {
            // 讓right找比tmp小的數(shù)
            while (right > left && array[right] >= tmp) {
                right--;
            }
            // 讓left找比tmp大的數(shù)
            while (left < right && array[left] <= tmp) {
                left++;
            }
            // 讓left與right這兩個數(shù)進行交換
            swap(array,left,right);
        }
        // 將基準值放到合適的位置
        swap(array,index,right);
        // 返回基準下標
        return right;
    }


    //前后指針法
    private static int partition2(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

    private static int minThree(int[]array,int left,int right) {
        //三數(shù)取中法，優(yōu)化遞歸實現(xiàn)的快速排序
        //使得最壞情況時，快速排序變?yōu)槎植檎?
        int mid = (left+right)/2;
        if(array[right] > array[left]) {
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
        if(array[mid] > array[left]) {
            return left;
        }
        if(array[mid] > array[right]) {
            return mid;
        }
        return right;
    }

    private static void swap(int[] array,int a,int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

}