- lomuto。易于理解
- Hoare。比较绕，效率比 lomuto 高。
lomuto
- 对于
[left, right] 区间，选取 left 作为基准点，将 [left+1...right] 区间分为三部分：1. 小堆（元素 < pivot） 2. 大堆（元素 >= pivot） 3. 乱堆（还未访问的元素）
- 使用两个指针：
1. lBound 指向小堆末尾元素 2. rBound 指向大堆末尾
static void quickSort(int[] nums, int left, int right) {
// base case
if (left >= right) return;
// partition
int pivot = nums[left]; // 轴心值
int lBound = left; // 指向小堆最后一个元素，等于 left 说明小堆为空
int rBound = left + 1;
// rBound 作为探子探索“乱堆”
while (rBound <= right) {
if (nums[rBound] >= pivot) {
// 找到大元素，放入大堆
rBound++;
} else {
// 找到小元素，放入小堆（将该元素与大堆第一个元素进行交换）
swap(nums, ++lBound, rBound++);
}
}
swap(nums, left, lBound); // 将小堆最后一个元素与 pivot 交换
// System.out.println("[" + left + ", " + right + "] " + Arrays.toString(nums));
// recursion
quickSort(nums, left, lBound);
quickSort(nums, lBound + 1, right);
}
Hoare
static void process(int[] nums, int left, int right) {
if (left >= right) return;
int pivot = nums[right]; // 右边界上的值作为“轴心”
int i = left, j = right - 1;
while (true) {
while (i < right && nums[i] <= pivot) i++;
while (left <= j && nums[j] > pivot) j--;
if (i > j) break;
swap(nums, i, j);
}
swap(nums, i, right);
process(nums, left, i - 1);
process(nums, i, right);
}
参考：