算法必知--- 快速排序（拓展应用）

写在前

基本思想：

先从数组中选择一个数作为划分值pivot，注意划分值随机选取。
进行区间划分的partition过程，小于pivot的放在左区间，大于pivot的放在右区间。
采用递归分治的思想划分左右子区间，注意保持区间不变性。

快排应用的注意点：

注意找前K大/前K小/第K大/第K小，是不需要对整个数组进行O(NlogN)的排序的！

因为可以通过快排切分直接O(N)找到第K大的数（比如求中位数就可以用本方法O(N)找到第mid大的数）

1.荷兰国旗问题

题目描述：

荷兰国旗问题：现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

荷兰国旗问题可以看成给定一个无序数组和目标值，将数组划分为大于、小于和等于目标值的三部分。本题实现返回等于目标值的区间。（划分值必须选中间元素）

思路分析：

两个关键点：划分函数partition（使用单向扫描分区）和划分主元pivot选取（使用num）。
具体实现是：定义两个边界less和more，可以把划分函数想象为向后推着大于的这部分。

代码实现：

public class NetherlandsFlag {
    public static int[] partition(int[] arr, int l, int r, int num) {
        int less = l - 1;
        int more = r + 1;
        while (l < more) {  // index指针复用l
            if (arr[l] < num) {
                swap(arr, ++less, l++);
            } else if (arr[l] > num) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        return new int[] {less + 1, more - 1};
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

75. 颜色分类，划分值选1！！

class Solution {
    public void sortColors(int[] nums) {
        int zero = -1, two = nums.length;
        int cur = 0;
        while (cur < two) {
            if (nums[cur] < 1) {
                swap(nums, ++zero, cur++);
            } else if (nums[cur] > 1) {
                swap(nums, --two, cur);
            } else {
                cur++;
            }
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

2.快速排序算法

思路分析：

基本实现：在荷兰国旗partition函数的基础上，我们对问题进行优化，我们可以使用递归分治的思想对左右子区间继续进行区间划分。注意：我们取每个区间的最后一个元素作为划分值pivot，为了避免时间复杂度退化（倒序情况下），我们取区间的随机值替换这个划分值。

复杂度分析：

时间复杂度 O(N log N)：库函数、快排等排序算法的平均时间复杂度为 O(N log N)。
空间复杂度 O(N) ：快速排序的递归深度最好（平均）为 O(log N) ，最差情况（即输入数组完全倒序）为 O(N)。

代码实现：

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) return;
    quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        // 取随机数与最后一个数进行调换，避免极端情况复杂度退化
        swap(arr, l + (int)(Math.random() * (r - l + 1)), r);
        int[] p = partition(arr, l, r);
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}
public static int[] partition(int[] arr, int l, int r) {
    int less = l - 1;
    int more = r;
    while (l < more) {
        if (arr[l] < arr[r]) {
            swap(arr, ++less, l++);
        } else if (arr[l] > arr[r]) {
            swap(arr, --more, l);
        } else {
            l++;
        }
    }
    // 把划分主元放到正确的位置
    swap(arr, more, r);
    return new int[] {less + 1, more};
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

3.快排进阶（应用）

描述：求解未排序数组中第K大的元素（leetcode215）/前K大个元素。

思路分析：求解第k大的元素，借助 partition 操作定位到最终排定以后索引为 nums.length - k 的那个元素（特别注意：随机化切分元素）,根据划分值继续决定结果所在区间，注意每次划分要随机选取划分值pivot（本题取区间随机值与区间尾元素交换，作为划分值），否则会严重影响效率。

代码实现：数组中第k大的元素

public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k == 0) return 0;
    int target = nums.length - k;
    return quickSort(nums, 0, nums.length - 1, target);
}

private int quickSort(int[] nums, int l, int r, int target) {
    int index = partition(nums, l, r);
    if (index == target) return nums[index];
    return index > target ? quickSort(nums, l, index - 1, target) : quickSort(nums, index + 1, r, target);
}

private int partition(int[] nums, int l, int r) {
    // 一定要随机选取划分值！
    swap(nums, l + (int)(Math.random() * (r - l + 1)), r);
    int less = l - 1, more = r;
    while (l < more) {
        if (nums[l] < nums[r]) {
            swap(nums, ++less, l++);
        } else if (nums[l] > nums[r]) {
            swap(nums, --more, l);
        } else {
            l++;
        }
    }
    swap(nums, more, r);
    return more;
}

public void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

partion划分函数也可以进行代码简化，原理相同。

private int partition(int[] nums, int l, int r) {
    swap(nums, l + (int)(Math.random() * (r - l + 1)), r);
    int less = l - 1, pivot = nums[r];
    for (int i = l; i < r; ++i) {
        if (nums[i] <= pivot) {
            swap(nums, ++less, i);
        }
    }
    swap(nums, less + 1, r);
    return less + 1;
}

描述：找到未排序数组的前k小个元素（剑指offer40）/第K小个元素。

思路：本题与上题思路相同，只不过注意两点：

注意：边界条件判断，basecase中k == 0情况！
第k小对应的索引值为k - 1。

代码：

public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0 || arr == null || arr.length == 0) return new int[0];
    // 注意：第k小的元素下标为k - 1
    return quickSort(arr, 0, arr.length - 1, k - 1);
}

private int[] quickSort(int[] arr, int l, int r, int k) {
    int index = partition(arr, l, r);
    if (index == k) {
        // 复制数组arr的前k个数，也就是0 - k-1
        return Arrays.copyOf(arr, index + 1);
    }
    return index > k ? quickSort(arr, l, index - 1, k) : quickSort(arr, index + 1, r, k);
}

private int partition(int[] arr, int l, int r) {
    // 随机选取划分值
    swap(arr, l + (int)(Math.random() * (r - l + 1)), r);
    int less = l - 1, pivot = arr[r];
    for (int i = l; i < r; ++i) {
        if (arr[i] <= pivot) {
            swap(arr, ++less, i);
        }
    }
    swap(arr, less + 1, r);
    return less + 1;
}

public void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}