public class c快速排序单向 {
    //单向扫描：循环一次（从左往右扫）
    //左指针i，为基准值+1；右指针j，为数组末尾值
    //左指针扫到比基准值大的和右指针值交换，右指针-1
    //右指针值更新基准值
    public static void sort(int[] arr,int start,int end){
        if(start<end){
            int index=getIndex2(arr,start,end);
            sort(arr,start,index);
            sort(arr,index+1,end);
        }

    }
    public static int getIndex2(int[] arr,int low,int high){
        int mid=arr[low];   //基准值
        int i=low+1;int j=high;
        while(i<=j){
            if(arr[i]<=mid){
                i++;
            }else{
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                j--;
            }
        }
        int temp=arr[low];   //更新主元的值
        arr[low]=arr[j];
        arr[j]=temp;
        return j;    //返回主元，根据主元划分
    }
    public static void main(String[] args) {
        int[] arr={1,9,2,5,7,3,4,6,8,0};
        sort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}