博客

思路浅解：首先对整个数组调用partition方法获取基值的中间位置，然后对两边分别调用快排。partition中，首先定义一个基值，定义一个变量i指向该基值应该在的位置。通过遍历确定i的位置。最终i的位置应该+1，原因是遍历中的i只是获得了比基值元素大的个数，而i应该为i+1

//定义一个快排
    public int partition(int[] a,int p,int r){
        int pivot = a[r];
        int i = p-1;
        for(int j=p;j<r;j++){
            if(a[j]<=pivot){
                i++;
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
        a[r] = a[i+1];
        a[i+1] = pivot;
        return i+1;
    }
    public void quickSort(int[] a,int p,int r){
        if(p<r){
            int q = partition(a,p,r);
            quickSort(a,p,q-1);
            quickSort(a,q+1,r);    
        }
    }