排序算法-快速排序

• 核心思想：选择一个基准值，然后将所有值一分为二，小于它的左分区，大于它的右分区，把它放左分区的队尾或者放右分区的对头，这样起码保证它自己到了它该在的位置上，然后对剩下的分区递归，重复上述步骤，每次保证基准值能到正确位置，直至所有都有序。

• 时间复杂度：O(nlogn)

• 空间复杂度：O(1)

   /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int basic = partition(arr, left, right);
        quickSort(arr, 0, basic - 1);
        quickSort(arr, basic + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        int basic = right; //选取队尾作为基准值
        for (int i = right - 1; i >= left; i--) {
            if (arr[i] > arr[right]) {
                basic--;//只要有比它大的，它正确位置就应该向左移动
                swap(i, basic, arr);
            }
        }
        //循环结束后，比基准大移动到了basic下标的后面
        //把基准值换到basic位置
        swap(right, basic, arr);
        //此时，基准值到了它应该在的位置
        return basic;
    }