快速排序算法概述
快速排序是一种高效的、基于比较的排序算法，采用分治（divide and conquer）策略。其核心思想是：从数组中选择一个元素作为“枢轴”（pivot），然后将数组分为两部分，使得所有小于枢轴的元素都位于枢轴之前，所有大于枢轴的元素都位于枢轴之后。这个过程称为“分区”（partition）。分区完成后，枢轴就处于其最终的排序位置。接着，对枢轴左右两边的子数组递归地重复这个过程，直到所有元素都排好序。
递归快速排序的常见实现问题
在实现递归快速排序时，开发者常遇到一些微妙的错误，导致排序结果不正确或出现栈溢出。这些问题通常集中在以下几个方面：
- 递归基准条件（Base Case）设置不当： 递归函数需要一个明确的终止条件，以防止无限递归。如果子数组只包含一个元素或为空，则无需进一步排序。
-
分区函数（partition）逻辑错误：
- 枢轴选择：枢轴的选择会影响性能，但更重要的是其在分区过程中的正确处理。
- 指针移动：左右指针的移动条件和停止条件必须精确，以确保所有元素都被正确比较和交换。
- 枢轴归位：分区结束后，枢轴必须被放置到正确的位置。
- 边界条件：当子数组非常小（例如只有两个元素）时，分区逻辑需要能正确处理。
- 递归调用范围不准确： 递归调用时，子数组的起始和结束索引必须正确，避免遗漏元素或重复处理。
修正后的快速排序实现
下面我们将通过一个修正后的Java实现来详细说明如何解决上述问题，构建一个健壮的快速排序算法。
1. quickSort 主入口方法
这个方法是公共接口，负责调用实际的递归排序方法。
public class QuickSort {
public static void quickSort(int[] s) {
if (s == null || s.length < 2) { // 处理空数组或单元素数组的边界情况
return;
}
quickSortSub(s, 0, s.length - 1);
}
// ... 其他方法
}2. quickSortSub 递归排序方法
这是快速排序的核心递归逻辑。
立即学习“Java免费学习笔记（深入）”；
private static void quickSortSub(int[] s, int a, int b) {
// 递归基准条件：当子数组至少包含两个元素时才进行分区和递归
// b - a >= 1 表示子数组长度至少为2 (b - a + 1 >= 2)
if (b - a >= 1) {
int point = partition(s, a, b); // 执行分区操作，获取枢轴的最终位置
// 递归排序左子数组
// 只有当左子数组至少包含两个元素时才递归，避免对单元素或空数组进行不必要的递归调用
if (point > a) { // point > a 意味着左子数组至少有一个元素
quickSortSub(s, a, point - 1);
}
// 递归排序右子数组
// 只有当右子数组至少包含两个元素时才递归
if (point < b) { // point < b 意味着右子数组至少有一个元素
quickSortSub(s, point + 1, b);
}
}
}关键修正点说明：
- if(b - a >= 1): 确保只有当子数组至少包含两个元素时才进行分区。如果 b - a 等于 0，表示只有一个元素，无需排序。原始代码 b - a > 1 会遗漏处理长度为2的子数组。
- if (point > a) 和 if (point < b): 这两个条件确保了递归调用是针对实际存在的、可能需要排序的子数组。例如，如果 point 等于 a，则左子数组为空，无需递归 quickSortSub(s, a, point - 1)。同样，如果 point 等于 b，则右子数组为空。这个修正比 if(point >= a + 2) 更通用和精确，避免了当 point 恰好是 a+1 时，左子数组只有一个元素仍进行递归的冗余。
3. partition 分区方法
分区方法是快速排序算法的灵魂，负责将数组分为两部分并放置枢轴。
private static int partition(int[] s, int a, int b) {
int pivot = s[b]; // 选择最右边的元素作为枢轴
int left = a; // 左指针，从子数组起始位置开始
int right = b - 1; // 右指针，从枢轴左边一个位置开始
while (left <= right) { // 循环直到左右指针相遇或交叉
// 移动左指针，直到找到一个大于或等于枢轴的元素
while (left <= right && s[left] < pivot) {
left++;
}
// 移动右指针，直到找到一个小于或等于枢轴的元素
while (left <= right && s[right] > pivot) {
right--;
}
// 如果左右指针尚未相遇或交叉，则交换它们指向的元素
if (left <= right) {
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
// 交换后，指针继续向内移动
left++;
right--;
}
}
// 循环结束后，left 指针指向第一个大于或等于枢轴的元素的位置
// 将枢轴放到其最终位置
int tmp = s[left];
s[left] = s[b]; // 将枢轴（s[b]）与 s[left] 交换
s[b] = tmp;
return left; // 返回枢轴的最终位置
}关键修正点说明：
- while(left <= right): 这是分区循环的正确条件。原始代码 while(left < right) 在某些情况下可能会提前终止，导致部分元素未被正确处理。
- 内部 while 循环条件 left <= right: 在内部循环中也需要检查 left <= right，以防止指针越界，尤其是在子数组已经排好序的情况下。
- 枢轴归位逻辑：循环结束后，left 指针将指向第一个大于或等于枢轴的元素位置。此时，将枢轴 s[b] 与 s[left] 交换，s[left] 就成了枢轴的最终位置。原始代码的枢轴归位逻辑 if(s[left] >= pivot) 是不必要的，且可能导致错误，因为 left 最终的位置就是枢轴应该在的位置。
4. 完整修正代码示例
public class QuickSort {
public static void quickSort(int[] s) {
if (s == null || s.length < 2) {
return;
}
quickSortSub(s, 0, s.length - 1);
}
private static void quickSortSub(int[] s, int a, int b) {
if (b - a >= 1) { // 确保子数组至少包含两个元素
int point = partition(s, a, b); // 执行分区操作
// 递归排序左子数组
if (point > a) { // 确保左子数组不为空
quickSortSub(s, a, point - 1);
}
// 递归排序右子数组
if (point < b) { // 确保右子数组不为空
quickSortSub(s, point + 1, b);
}
}
}
private static int partition(int[] s, int a, int b) {
int pivot = s[b]; // 选择最右边的元素作为枢轴
int left = a; // 左指针
int right = b - 1; // 右指针
while (left <= right) { // 循环直到左右指针相遇或交叉
// 移动左指针
while (left <= right && s[left] < pivot) {
left++;
}
// 移动右指针
while (left <= right && s[right] > pivot) {
right--;
}
// 如果指针未交叉，则交换元素
if (left <= right) {
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
// 将枢轴归位
int tmp = s[left];
s[left] = s[b];
s[b] = tmp;
return left; // 返回枢轴的最终位置
}
public static void main(String[] args) {
int[] arr = {85, 10, 24, 63, 45, 27, 100, 31, 96, 50, 40, 23, 49, 96, 120, 105, 13, 5, 42, 69, 22, 12};
System.out.println("原始数组:");
for (int i : arr) System.out.print(i + ", ");
System.out.println("\n");
quickSort(arr);
System.out.println("排序后数组:");
for (int i : arr) System.out.print(i + ", ");
System.out.println("");
}
}测试输出：
原始数组: 85, 10, 24, 63, 45, 27, 100, 31, 96, 50, 40, 23, 49, 96, 120, 105, 13, 5, 42, 69, 22, 12, 排序后数组: 5, 10, 12, 13, 22, 23, 24, 27, 31, 40, 42, 45, 49, 50, 63, 69, 85, 96, 96, 100, 105, 120,
可以看到，经过修正后的代码能够正确地对数组进行排序。
总结与注意事项
正确实现快速排序需要对递归基准条件和分区逻辑有深入的理解。以下是一些关键点：
- 递归基准条件： 确保当子数组长度为0或1时，递归停止。if (b - a >= 1) 是一个可靠的判断。
-
分区逻辑：
- 左右指针的移动条件和停止条件必须精确，通常是 while (left <= right) 外部循环和 while (left <= right && condition) 内部循环。
- 枢轴的最终位置必须正确确定，并将其与 left 指针最终指向的元素进行交换。
- 递归调用范围： 在递归调用 quickSortSub 时，确保传递的子数组索引是正确的，并且避免对空或单元素子数组进行不必要的递归。if (point > a) 和 if (point < b) 提供了精确的边界检查。
- 枢轴选择： 本教程中选择了子数组的最右侧元素作为枢轴。虽然简单，但在处理已排序或逆序数组时可能导致最坏情况性能（O(n^2)）。更优的枢轴选择策略包括随机选择或三数取中法，以提高算法的平均性能。
通过遵循这些最佳实践，可以构建出高效且鲁棒的快速排序算法。
