package partition;

import java.util.Arrays;

public class Test1 {
    public static void main(String[] args) {
        int[] numbers={1,2,3,4,5,6,0,7,8,9,10,0};
        partitionSort(numbers,0,numbers.length-1);
//        for (int n:numbers) {
//            System.out.println(n);
//        }
    }

    private static void partitionSort(int[] numbers,int left,int right) {
        if (left>=right){
            return;
        }
        int mid = partition(numbers, left, right);
        partitionSort(numbers,left,mid-1);
        partitionSort(numbers,mid+1,right);
    }

    static int partition(int[] s,int left ,int right){
        int pivot=s[right];
        int i=left;
        int j=left;
        while (i<right&&j<right){
            if (s[i]>s[j]&&s[j]<pivot){
                int temp=s[j];
                s[j]=s[i];
                s[i]=temp;
                j++;
                i++;
                continue;
            }
            if (s[i]<pivot&&s[i]<s[j]){
                i++;
            }
            j++;
        }
        if (s[i]>pivot){
            int tempt=s[i];
            s[i]=pivot;
            s[right]=tempt;
        }

        System.out.println(Arrays.toString(s));
        return i;
    }
}

无参考的，代码比较臃肿。使用类似归并排序的树形递归结构，很容易打出来，这个代码哨兵花费大量时间去调试，关于哨兵，记住一个重点
i索引递增的两种情况，
第一种情况：s[i]>s[j]并且s[j]<pivot的值，i索引+1
第二种情况：s[i]小于pivot并且s[i]小于s[j]。
还有就是s[i]和pivot的交换条件 s[i]必须大于pivot的值，交换才有意义，否则会有问题