写在前
基本思想：
- 先从数组中选择一个数作为划分值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; }
