快速排序的一种Java实现

1. 双指针交换法；
2. pivot选取中点；

   public int partition(int[] arr, int sta, int end) {

        int pivot = arr[sta + (end-sta)/2];
        while (sta < end) {
            while (arr[sta] < pivot) {
                sta++;
            }
            while (arr[end] > pivot) {
                end--;
            }
            if (sta < end) {
                int temp = arr[sta];
                arr[sta++] = arr[end];
                arr[end--] = temp;
            }
        }

        return sta;
    }

    public void qSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }

        int idx = partition(arr, head, tail);
        qSort(arr, head, idx-1);
        qSort(arr, idx+1, tail);
    }


    @Test
    public void testQsort() {
        System.out.println("=== 7, 6, 5 ==");
        int[] arr = new int[] {7, 6, 5, 8};
        qSort(arr, 0, arr.length-1);
        for(int a : arr) {
            System.out.println(a);
        }

        System.out.println("=== 5, 6, 7 ==");
        int[] arrA = new int[] {5, 6, 7};
        qSort(arrA, 0, arrA.length-1);
        for(int a : arrA) {
            System.out.println(a);
        }

        System.out.println("=== 5, 5, 5 ==");
        int[] arrB = new int[] {5, 5, 5};
        qSort(arrB, 0, arrB.length-1);
        for(int a : arrB) {
            System.out.println(a);
        }

        System.out.println("=== 6,6, 5, 5, 5, 7 ==");
        int[] arrC = new int[] {6, 6, 5, 5, 5, 7};
        qSort(arrC, 0, arrC.length-1);
        for(int a : arrC) {
            System.out.println(a);
        }
    }