死磕排序算法：手撕快速排序的四种姿势（Hoare、挖坑、前后指针 + 非递归）

文章目录

• 一、快速排序的核心思想
• 二、三种切分方法
• • 1.Hoare 法（左右指针法）
  • • 疑惑点
  • 2.挖坑法
  • 3.前后指针法
• 三、非递归实现 (Stack 版本)
• 四、总结

一、快速排序的核心思想

快速的精髓在于“分治”，即每一轮只做一件事：选一个基准值，把比它小的丢左边，比它大的丢右边，最后当基准值归位后，它左右两边的区间就成为了两个独立的子问题，直接递归处理就行。

速记： 选基—划区—递归

代码框架

public static void quickSort(int[] array) {
quick(array, 0, array.length – 1);
}

private static void quick(int[] array, int start, int end) {
if (start >= end) {
return;
}
int pivot = partition(array, start, end);
quick(array, start, pivot – 1);
quick(array, pivot + 1, end);
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
//核心方法
private static int partition(int[] array, int left, int right)

二、三种切分方法

1.Hoare 法（左右指针法）

这是快排发明者 Hoare 最初提出的版本

核心逻辑：

• 选取最最左边（left）的元素作为基准值（key）
• 让right指针先走，去找比key小的数
• left指针再向右走，找比key大的数
• 交换他们两个的值
• 重复该流程，直到他们相遇，最后将基准值与相遇点交换

// Hoare版本核心代码
private static int partition(int[] array, int left, int right) {
int i = left;
int key = array[left]; // 选最左边做基准
while (left < right) {
// 必须右边先走！找比 key 小的
while (left < right && array[right] >= key) {
right—;
}
// 左边后走，找比 key 大的
while (left < right && array[left] <= key) {
left++;
}
swap(array, left, right);
}
swap(array, left, i); // 基准值归位
return left;
}

疑惑点

疑问 1：为什么要限制 left < right？ Q： 外层循环已经有了 while(left < right)，为什么里面的小循环还要加这个判断？ A: 防止越界(IndexOutOfBounds) eg：如果数组{1,2,3,4,5}这种情况下，基准值为1，right指针会一直找比1小的数，但是一直找不到，会一直减，由于没有left < right拦着，right会减到-1，直接报错

疑问 2：为什么必须取“等于” (>= 和 <=)？ Q： 我写成 array[right] > key ，不加 = 可以吗？ A：不行，会死循环 eg：假如数组是 {5, 5, 2…}，基准是 5。 left指针指向 5，不满足 <5，停下，right指针指向 5，不满足 >5，停下，两人交换，数组还是 {5, 5…} 下一轮循环，两人又都在原地停下，再次交换……陷入死循环

疑问 3：最关键的——为什么要“右边先走”？ Q： 我先移动左指针不行吗？ A：绝对不行（当基准在左边时）。

• 当到最后一步是 swap(array, left, i)，也就是把相遇点的数和基准值交换。

• 基准值在最左边，所以我们希望交换到最左边的那个数，必须是比基准值小的。

• 右边先走：right 会停在比基准小的地方。此时 left 撞上来，相遇点就是“小”的。

• 左边先走：left 会停在比基准大的地方。此时 right 撞上来，相遇点就是“大”的。把大的换到最左边，排序就错了

总结：基准在左，右边先走；俩人停下，互相交换。

2.挖坑法

既然 Hoare 法还要考虑左右谁先走，还要考虑最后一步交换逻辑，那么主播主播，有没有更强势的写法？ 当然有，那就是挖坑法

核心逻辑：

• 把基准值存入临时变量key，此时left 指针位置形成第一个"坑"。
• right指针找小于key，找到了直接填到左边的坑里（right指针现在的位置变新坑)。
• left指针找大于key，找到了直接填到右边的坑里（left现在位置变新坑)。
• 相遇时，把 key 填入最后的坑中

//挖坑法版本核心代码
private static int partition(int[] array, int left, int right) {
int key = array[left]; // 1. 挖坑
while (left < right) {
// 2. 右边找小，填左坑
while (left < right && array[right] >= key) {
right—;
}
array[left] = array[right];

// 3. 左边找大，填右坑
while (left < right && array[left] <= key) {
left++;
}
array[right] = array[left];
}
// 4. 填最后的坑
array[left] = key;
return left;
}

总结：先挖基准，右填左，左填右，最后再把基准填上

3.前后指针法

这种方法逻辑稍微抽象一点，虽然代码看着短，但逻辑稍微绕一点，但是它的优势是不需要从右往左遍历，适合链表

核心逻辑：

• prev 指向基准，cur 指向下一个

• 当cur 遇到比基准小的数时： prev 向前扩一步 交换 prev 和 cur 的值（把小的拉进圈子，把大的挤出去）

• 最后交换基准值和 prev

// 前后指针法版本核心代码
private static int partition3(int[] array, int left, int right) {
int prev = left;
int cur = left + 1;
//prev 指向 0 (基准值位置)，cur 指向 1 (下一个)。

int key = array[left];

//只有当 cur 遇到比 key 小的数时，才需要处理
while (cur <= right) {
// 核心判断：只在遇到“小的”时候处理
// if (array[cur] < key && ++prev != cur)
// 条件 A: array[cur] < key -> 找到了属于左边的数
// 条件 B: ++prev != cur -> 这是一个优化。
// 如果 prev 紧贴着 cur (中间没夹着大数)，比如开头全是小的，
// 那 prev 往前走一步就撞上 cur 了，自己换自己没必要。
// 只有当 prev 和 cur 之间有空隙（夹着大数）时，才需要真正的交换。
// 下面的是简化版本
if (array[cur] < key) {
prev++;
if (prev != cur) {
swap(array, cur, prev);
}
}
//不管是不是比 key 小，cur 都要继续往后走，去检查下一个数
cur++;
}
// 循环结束，prev 指向的是最后一个比 key 小的数
// 把基准值(key)换到这里，让它居中
swap(array, left, prev);
return prev;
}

三、非递归实现 (Stack 版本)

如果数据量超级大，或者数组本身就有序，递归层数太深会导致 StackOverflowError。这时候必须使用非递归写法

非递归的核心是：自己造一个栈，模拟系统递归的过程

核心思路： 不用计算机来进行递归，我们自己造一个 Stack 来存任务。

• 创建一个 Stack

• 把整个数组的 left 和 right 压入栈

• 循环弹栈 -> 切分 (调用partition) -> 得到基准 pivot

• 如果 pivot 左边还有元素，把左区间的范围压栈

• 如果 pivot 右边还有元素，把右区间的范围压栈

• 注意顺序： 入栈如果是“先左后右”，出栈就是“先右后左”

import java.util.Stack;

public static void quickSortNonRecursive(int[] array) {
Stack<Integer> stack = new Stack<>();

// 放入整个数组 (先放左，再放右)（放下标）
stack.push(0);
stack.push(array.length – 1);

while (!stack.isEmpty()) {
// 取出 (注意顺序：先出右，再出左)
int right = stack.pop();
int left = stack.pop();

// 调用之前的 partition 方法
int pivot = partition(array, left, right);

// 右边新任务 (如果元素 > 1个)
if (pivot + 1 < right) {
stack.push(pivot + 1);
stack.push(right);
}

// 左边新任务 (如果元素 > 1个)
if (left < pivot – 1) {
stack.push(left);
stack.push(pivot – 1);
}
}
}

四、总结