快排code demon

快速排序demon

/**
 * @author river
 * @date 2019/1/17 13:59
 **/
public class QuiteSortDemon {

    public void quitSort(int[] num)
    {
        quitSort_c(num,0,num.length - 1);
    }
    public void quitSort_c(int[] num,int start,int end)
    {
        if(start >= end){
            return;
        }

        int middle = partition(num,start,end) ;
        quitSort_c(num,start,middle -1);
        quitSort_c(num,middle + 1,end);
    }
    /**
     * 返回分割数下标，
     * 并将 小于 分割数的 放置于左边，
     * 大于 分割数的 放置于右边
     **/
    public int partition(int[] num,int start,int end){
        //保存已经按照规则排序的下标
        int i = start;
        int patitionValue = num[end];
        //遍历整个数组
        for (int j = start; j <= end ; j++) {
            if(num[j] < patitionValue){
                int tmp = num[j];
                num[j] = num[i];
                num[i] = tmp;
                i++;
            }
        }
        //最后将 pation value 放置于合适位置
        int tmp = num[i];
        num[i] = num[end];
        num[end] = tmp;
        return i;
    }

    public static void main(String[] args) {
        int[] b = {5,1,9,3,7,8,12,666,888,45,221};
        new QuiteSortDemon().quitSort(b);
        System.out.println(new Gson().toJson(b));
    }
}