import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int arr[]) {
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int arr[], int left, int right) {

        if(left >= right) {
            return;
        }

        int pivot = arr[left]; // 取子集中左边第一个数为基准
        int i = left;
        int j = right;

        while(i < j) {

            while(i < j && arr[j] >= pivot) {   // j从右边开始寻找一个比基准小的数
                j--;
            }

            if(i < j) { // 执行到这里，即j已经找到了一个数比基准小，且i和j未相遇
                arr[i++] = arr[j];    // 将j所指向的数，填入i所指向的格子
            }

            while(i < j && arr[i] < pivot) {    // i从左边开始寻找一个比基准大或等于基准的数
                i++;
            }

            if(i < j) { // 执行到这里，即i已经找到了一个数比基准大或相等，且i和j未相遇
                arr[j--] = arr[i];    // 将i所指向的数，填入j所指向的格子
            }

        }

        arr[i] = pivot;     // 将基准填回arr[i]
        sort(arr, left, i - 1);     // 对左边的子集进行递归排序
        sort(arr, i + 1, right);    // 对右边的子集进行递归排序

    }

    public static void main(String[] args) {

        int a[] = { 16, 23, 5, 15, 14, 16, 5, 33 }; // 输出 [5, 5, 14, 15, 16, 16, 23, 33]
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }

}