快排

快排

看完此篇，你便可以去来练下手：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/submissions/

基本思想：采用 分治

• 确定一个边界：q[l]，q[ l + r >> 1]，q[r]
• 调整范围：边界左边小于等于边界，边界右边大于等于边界 -> 左区间的最大值小于等于右区间的最小值
  • 如何优雅来进行范围的调整？
  • 可以采用 双指针做法，这也避免了额外空间，同样是线性扫描
  • 每次循环，左右指针先进行移位后，再来进行逻辑判断
• 递归处理左右两段

快排模板

    static int[] quickSort(int[] arr, int l, int r) {

        if (l >= r) return arr;
        int x = arr[l] + arr[r] >> 1, i = l - 1, j = r + 1;
        while (i < j) {
            do {
                i ++;
            } while (arr[i] < x);
            do {
                j --;
            } while (arr[j] > x);

            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        // 递归
        // 取 j,x便不能为 arr[r]
        // 取 i,x便不能为 arr[l]
        // 否则便会有边界问题
        quickSort(arr, l, j);
        quickSort(arr, j + 1, r);

        return arr;
    }

衍生出来的快速查找算法，寻找第 k小的数，每次递归时只需要递归一个区间即可

    // 快速选择 寻找第 k小的数
    // 每次只需递归处理一半即可
    static int quick_find(int[] arr, int l, int r, int k) {
        if (l == r) return arr[l];
        int x = arr[l] + arr[r] >> 1, i = l - 1, j = r + 1;
        while (i < j) {
            while (arr[++ i] < x);
            while (arr[-- j] > x);

            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }

        }
        int len = j - l + 1;
        if (len >= k) return quick_find(arr, l, j, k);
        return quick_find(arr, j + 1, r, k - len);
    }