兩邊扔 ;雙邊指針

public class QuickSorting {

    private static int doublePointerSwap(int[] arr, int startIndex,int endIndex){
        int pivot = arr[startIndex];
        int leftPoint = startIndex;
        int rightPoint = endIndex;


        while (leftPoint < rightPoint) {

            /**
             * 因?yàn)槭切?>大，所以下面兩個(gè)while不能交換位置，第一個(gè)while必須是找到小值
             */

            //從右往左找，知道找到比pivot小的值的下標(biāo)
            while (leftPoint < rightPoint && arr[rightPoint] >= pivot) {
                rightPoint--;
            }

            //從左往右找，直到找到比pivot大的值的下標(biāo)
            while (leftPoint < rightPoint && arr[leftPoint] <= pivot) {
                leftPoint++ ;
            }

            //找到后，交換兩者的值
            if (leftPoint < rightPoint) {
                int temp = arr[leftPoint];
                arr[leftPoint] = arr[rightPoint];
                arr[rightPoint] = temp;
            }
        }

        //一輪完畢后，雙邊指針重合
        arr[startIndex] = arr[leftPoint];
        arr[rightPoint] = pivot;
        //返回分界值所在的標(biāo)
        return leftPoint;
    }

    public static void quickSort(int[] arr, int startIndex,int endIndex) {
       if (startIndex < endIndex) {  //if 必須要有 不然沒(méi)有循環(huán)退出條件
           int delimiterIndex = doublePointerSwap(arr, startIndex, endIndex);
           quickSort(arr,startIndex,delimiterIndex-1);
           quickSort(arr,delimiterIndex+1,endIndex);
       }

    }


    public static void main(String[] args) {
        int[] arr = {101,34,39,1,-1,3,1,90,123,10};

        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}