算法练习(22) - 快排:原址排序

public class QuickSortTest {

    @Test
    public void quickSort_test() {
        int[]  a = {1,9,3,4,7,2,9,10,14,16};
        quickSort(a,0,a.length-1);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
            System.out.print(",");
        }
    }

    private void quickSort(int[] a, int p, int q) {
       if(p<q){
           int r = partition(a,  p,  q);
           quickSort(a,p,r-1);
           quickSort(a,r+1,q);
       }
    }

    private int partition(int[] a, int p, int q) {

        int x = a[q];
        int point = p-1;
        for (int i = p; i < q; i++) {
            if(a[i] < x){
                point ++;
                int temp = a[i];
                a[i] = a[point];
                a[point] = temp;
            }
        }

        int temp = a[point+1];
        a[point + 1 ] = a[q];
        a[q] = temp;
        return point +1;
    }

}