前言
快速排序（quickSort）
partition - 划分 快速排序的核心子操作，二路划分/快速选择中显式调用，三路划分中内联调用
二路划分
Hoare - 快排的原始分区方案 双指针 性能优先 pivot需要交换到边界 划分后pivot不保证在最终位置
Lomuto - 简洁的单指针算法 pivot需要交换到边界 划分后pivot在最终位置
三路划分 - 应对重复元素 pivot不需要交换到边界 partition内联在算法中
快速选择（quickSelect）- 基于partition
掌握目标：
题目
经典Hoare
特点：双指针从两端向中间，而pivot不需要归为到最终位置
import java.util.Random;
class Solution {
// 静态 Random，避免每次递归都创建新对象，同时保证随机性
private static final Random RANDOM = new Random();
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
/**
* 快速排序主函数
* @param nums 待排序数组
* @param left 当前区间左边界（闭）
* @param right 当前区间右边界（闭）
*/
private void quickSort(int[] nums, int left, int right) {
// 递归终止：区间为空或只有一个元素
if (left >= right) return;
// 经典 Hoare 分区：返回分界点 j
int j = partition(nums, left, right);
// 注意：Hoare 分区不保证 pivot 归位
// 分区后：[left, j] <= pivot, [j+1, right] >= pivot
quickSort(nums, left, j);
quickSort(nums, j + 1, right); }
/**
* 经典 Hoare 分区
* @return 分界点 j，满足 [left, j] <= pivot, [j+1, right] >= pivot
*/
private int partition(int[] nums, int left, int right) {
// 随机选一个基准值（注意：选的是值，不是下标）
int pivot = nums[left + RANDOM.nextInt(right - left + 1)];
// i 从左向右扫描，j 从右向左扫描
// 初始值放在边界外一格，配合 do-while 使用
int i = left - 1;
int j = right + 1;
while (true) {
// 从左往右找第一个 >= pivot 的元素
do {
i++;
} while (nums[i] < pivot);
// 从右往左找第一个 <= pivot 的元素
do {
j--;
} while (nums[j] > pivot);
// 如果 i >= j，说明扫描相遇，分区结束
if (i >= j) {
return j;
}
// 交换逆序对
swap(nums, i, j);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}912.排序数组
class Solution {
// 防止数组有序，时间复杂度退化，使用随机基准
// 防止递归多次调用，使用静态成员
private static final Random random = new Random();
public int[] sortArray(int[] nums) {
// 快速排序，三路划分
quickSort(nums,0,nums.length - 1);
return nums;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// quickSort传入一个数组和排序的左右边界，对数组进行快排
public void quickSort(int[] nums, int left, int right) {
// 递归需要一个结束条件
if (left >= right) return;
// 随机基准应取[left,right] nextInt中传参-1为随机值的范围
int pivotIndex = left + random.nextInt(right - left + 1);
int pivot = nums[pivotIndex];
int i = left;// 当前扫描位置
int lt = left; // less than 小于区的右边界 + 1 / 下一个“小于pivot”的元素该放的位置
int gt = right;// greater than 大于区的左边界 - 1 / 下一个“大于pivot”的元素该放的位置
// 三路划分
// 未处理空间是 [i,gt]
// 当i == gt时，i/gt处元素还没有处理
while (i <= gt) {
if (nums[i] < pivot) {
// 小于pivot的元素需要与lt交换，交换后遍历下一个元素 i++ 且lt++
swap(nums, i, lt);
lt++;
i++;
} else if (nums[i] > pivot) {
// 大于pivot元素 与gt交换，gt-- 交换后原来gt处的元素交换到i处，还没有处理，所以i不动
swap(nums, i, gt);
gt--;
} else {
// 与pivot相同，没有出现小于或大于，lt和gt都不需要动，只要遍历下一个元素即可 i++
i++;
}
}
// 循环结束之后，只是划分了 < pivot = pivot > pivot
// [lt,gt]元素与pivot相同
// 递归划分小于区和大于区
quickSort(nums, left, lt - 1);
quickSort(nums, gt + 1, right);
}
}