17-快速排序

1. 基本思想

概述
- 快速排序(Quicksort) 是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序；排序的方式是当两个子数组都有序时整个数组也就自然有序了。
- 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
切分元素 arr[x]
- 该元素值又被称为"基准数" / "中轴"
- 一般选取数组首元素、尾元素、中间元素作为切分元素
- 作用：将数组分割成两个子数组，其中一个子数组的元素都比基准数小，另一个子数组的元素都比基准数要大。
切分方法 partition(arr, left, right)
- 快速排序递归地将子数组 arr{left, right} 排序，每调用一次 partition 就会使基准数 arr[x] 放到最终位置，然后再递归调用 partition 将其他位置的元素排序。
- 切分过程使得数组满足下面 3 个条件:
  - 对于某个 x，arr[x] 已经排定
  - arr[left] 到 arr[x-1] 的所有元素都小于 arr[x]
  - arr[x+1] 到 arr[right] 的所有元素都不小于 arr[x]
- 因为切分过程总是能排定一个元素，用归纳法不难证明递归能够正确地将数组排序：如果左子数组和右子数组都是有序的，那么左子数组(有序且没有任何元素大于切分元素)、切分元素和右子数组(有序且没有任何元素小于切分元素)组成的结果数组也一定是有序的。切分算法就是实现了这个思路的一个递归程序。
切分过程
- 先从数组中选定一个切分元素作为基准数
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
- 再对左右区间重复 step2，直到各区间只有一个数

2. 标配

平均时间复杂度：O(NlogN)
最坏时间复杂度：O(N^2)
最好时间复杂度：O(NlogN)
空间复杂度：O(logN)

3. 挖坑填数

i = left, j = right; 将基准数挖出而形成了第一个坑 arr[i]
j-- 由后向前找比基准数小的数，找到后挖出此数填入前面一个坑 arr[i] 中
i++ 由前向后找比基准数大的数，找到后也挖出来填到前面一个坑 arr[j] 中
再重复执行 step2，step3 两步，直到 i == j，将基准数填入 a[i] 中

4. 代码实现

public class QuickSort2 {
    public static void main(String[] args) {
        int[] arr = {5, 9, 78, 0, 23, -567, 70, 42, -5, 36};
        quickSort_2(arr, 0, arr.length-1);
        print(arr);
    }

    public static void quickSort_1(int[] arr, int left, int right) {
        // 分治
        if (left < right) {
            int x = partition(arr, left, right);
            quickSort_1(arr, left, x-1);
            quickSort_1(arr, x+1, right);
        }
    }

    /**
     * 递归调用切分方法完成子数组排序
     * @param arr 待排序数组
     * @param left 数组首元素索引
     * @param right 数组尾元素索引
     * @return 切分元素的最终存放位置
     */
    public static int partition(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        int pivot = arr[i]; // 挖出左边的, 待会要先从右边找

        while (i < j) {
            // 1. 先从右向左找小于 pivot 的数来填 arr[i] 的坑
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) arr[i++] = arr[j];

            // 2. 再从左向右找大于/等于 pivot 的数来填 arr[j] 的坑
            while (i < j && arr[i] < pivot) i++;
            if(i < j) arr[j--] = arr[i];
        }

        // 退出时 i == j; 该位置也是 pivot 在数组中的最终位置
        arr[i] = pivot;
        return i;
    }


    public static void quickSort_2(int[] arr, int left, int right) {
        if (left < right) {
            int i = left;
            int j = right;
            int pivot = arr[right]; // 挖右, 始左

            while (i < j) {
                while (i < j && arr[i] < pivot) i++;
                if(i < j) arr[j--] = arr[i];
                while (i < j && arr[j] >= pivot) j--;
                if(i < j) arr[i++] = arr[j];
            }

            arr[i] = pivot;
            quickSort_2(arr, left, i-1);
            quickSort_2(arr, i+1, right);
        }
    }

    public static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

5. Tips

while 里 i < j 的判断一个都不能少！
想一想就俩元素的时候，快排是怎么个情况?
N 个元素，一共 logN 层，每层都是 O(N)，一共 NlogN
每选出一个 pivot 对其 partition 过后，也就确定了这个数最终在数组中的位置
有的 pivot 是随机从数组中选的一个数，这个咋弄？选出来之后直接让它和 arr[left/right] 做交换