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