public class d快速排序双向 {
    //双向扫描：
    //      与单向扫描不同的是双重循环
    //      左指针比基准值大的值和右指针比基准值大的值交换
    public static void sort(int[] arr,int start,int end){
        if(start<end){
            int index=getIndex1(arr,start,end);
            sort(arr,start,index);
            sort(arr,index+1,end);
        }

    }
    public static int getIndex1(int[] arr,int low,int high){
        int mid=arr[low];   //基准值
        int i=low+1;int j=high;
        while(i<=j){
            while(i<=j&&arr[j]>=mid){
                j--;
            }
            while(i<=j&&arr[i]<=mid){
                i++;
            }
            if(i<j){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        //将循环后j的值赋给low，换更新主元
        int temp=arr[low];
        arr[low]=arr[j];
        arr[j]=temp;

        return j;
    }
    public static int getIndex2(int[] arr,int low,int high){
        int temp=arr[low];   //基准值
        while(low<high){
            while(low<high&&arr[high]>=temp){
                high--;
            }
            arr[low]=arr[high];
            while(low<high&&arr[low]<=temp){
                low++;
            }
            arr[high]=arr[low];
        }
        arr[low]=temp;
        return low;
    }
    public static void main(String[] args) {
        int[] arr={1,9,2,5,7,3,5,6,8};
        sort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}