快速排序算法概述
快速排序（quicksort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”。它通过选择一个“基准”（pivot）元素，将数组划分为两个子数组：一个子数组中的所有元素都小于基准，另一个子数组中的所有元素都大于基准。然后，对这两个子数组递归地进行快速排序，直到整个数组有序。
一个典型的快速排序实现包含以下几个关键步骤：
- 选择基准（Pivot Selection）：从数组中选择一个元素作为基准。常见的选择包括第一个元素、最后一个元素、中间元素或随机元素。
- 分区（Partitioning）：重新排列数组，使得所有小于基准的元素都移到基准的左边，所有大于基准的元素都移到基准的右边。基准元素现在位于其最终的排序位置。
- 递归排序（Recursive Sort）：对基准左右两边的子数组分别递归地进行快速排序。
常见实现问题分析
以下是一个尝试实现快速排序的Java代码示例，但在实际运行中发现排序结果不正确：
public class QuickSort {
public static void quickSort(int[] s) {
quickSortSub(s, 0, s.length - 1);
}
private static void quickSortSub(int[] s, int a, int b) {
// 原始问题：当子数组长度为2时（b-a=1），此条件不满足，导致无法排序
if(b-a > 1) {
int point = partition(s, a, b);
quickSortSub(s, a, point - 1);
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) { // 原始问题：当right越过a时，循环可能继续，导致left和right指向相同元素时仍尝试交换
while(s[left] < pivot) {
left++;
}
while(s[right] > pivot) {
right--;
}
if(left < right) { // 避免left和right交叉后进行交换
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
// 原始问题：此处将基准元素 s[b] 与 s[left] 交换，但没有检查 s[left] 是否真的大于或等于基准
s[b] = s[left];
s[left] = pivot;
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};
quickSort(arr);
for (int i: arr) System.out.print(i + ", ");
System.out.println("");
// 预期输出：5, 10, 12, 13, 22, 23, 24, 27, 31, 40, 42, 45, 49, 50, 63, 69, 85, 96, 96, 100, 105, 120
// 实际输出：5, 10, 12, 22, 13, 23, 24, 31, 27, 40, 42, 45, 49, 50, 63, 69, 85, 96, 96, 100, 120, 105 (部分元素未正确排序)
}
}上述代码的输出显示数组并未完全排序。通过分析，我们发现主要问题出在 quickSortSub 的递归终止条件和 partition 方法的循环逻辑及最终交换上。
修正与优化
针对上述问题，我们对代码进行以下修正：
立即学习“Java免费学习笔记（深入）”；
-
quickSortSub 方法的递归终止条件：
- 原始条件 b-a > 1 意味着只有当子数组长度大于2时才进行排序。当子数组长度为2（例如 a=0, b=1）时，b-a 为1，不满足条件，导致长度为2的子数组无法被排序。
- 应将条件放宽至 b-a >= 1 或 a
-
quickSortSub 方法的递归调用前检查：
- 在某些极端情况下，例如当基准元素是子数组中的最小或最大值时，point - 1 可能会小于 a，或者 point + 1 可能会大于 b。虽然在一般情况下，这些递归调用会立即被基准条件 b-a >= 1 阻止，但显式地添加检查可以增强代码的健壮性，避免不必要的递归栈深度。
- 例如，if(point >= a+2) 确保左侧子数组至少有两个元素需要排序，否则无需递归。
-
partition 方法的循环条件：
- 原始 while(left
- 应在 while(left a 的条件，以防止 right 指针超出有效范围，尤其是在基准元素是最小值时。
-
partition 方法的基准元素最终归位：
- 在 partition 循环结束后，left 指针指向的元素 s[left] 是第一个大于或等于基准的元素。基准元素 s[b] 应该与 s[left] 交换，以将基准放置到其最终的排序位置。
- 但需要确保 s[left] 确实是应该被交换的元素。如果 left 已经越过了 right 或者 s[left] 实际上小于基准（这通常不应该发生，但在某些极端情况下可能需要更精细的判断），直接交换可能导致错误。
- 更安全的做法是：在循环结束后，left 指针将指向基准元素最终应该放置的位置。如果 s[left] 大于或等于基准，那么将 s[b]（即基准）与 s[left] 交换，然后返回 left 作为基准的新位置。
修正后的代码示例
public class QuickSort {
public static void quickSort(int[] s) {
quickSortSub(s, 0, s.length - 1);
}
private static void quickSortSub(int[] s, int a, int b) {
// 修正1: 确保子数组长度为2时也能进入排序
if (b - a >= 1) {
int point = partition(s, a, b);
// 修正2: 递归调用前检查子数组是否至少有两个元素，避免不必要的递归
if (point >= a + 1) { // 至少有一个元素 (point-1 >= a)
quickSortSub(s, a, point - 1);
}
if (point <= b - 1) { // 至少有一个元素 (point+1 <= 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;
// 修正3: 增加 right > a 条件，防止 right 越界，并确保left和right指针正确移动
while (left <= right) { // 循环条件应为 <=，当 left == right 时也可能需要处理
while (left <= right && s[left] < pivot) { // left不能越过right
left++;
}
while (left <= right && s[right] > pivot) { // right不能越过left
right--;
}
if (left <= right) { // 确保left和right未交叉或重合时才进行交换
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++; // 交换后，移动指针
right--; // 交换后，移动指针
}
}
// 修正4: 将基准元素放到正确的位置
// 循环结束后，left 指针指向第一个大于或等于 pivot 的元素，
// 或者如果所有元素都小于 pivot，则 left 会越过 b。
// right 指针指向最后一个小于或等于 pivot 的元素。
// 此时，left 指针是基准元素应该放置的位置。
// 将基准元素 s[b] 与 s[left] 交换。
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("");
}
}修正后的 partition 方法的另一种常见且更简洁的实现方式（Hoare分区方案）：
private static int partitionHoare(int[] s, int a, int b) {
int pivot = s[a]; // 选择第一个元素作为基准
int left = a - 1;
int right = b + 1;
while (true) {
do {
left++;
} while (s[left] < pivot);
do {
right--;
} while (s[right] > pivot);
if (left >= right) {
return right; // 返回基准的最终位置
}
// 交换 s[left] 和 s[right]
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}注意： 如果使用 partitionHoare 这种方式，quickSortSub 的递归调用需要调整为 quickSortSub(s, a, point); 和 quickSortSub(s, point + 1, b);，因为 point 返回的是最后一个小于或等于基准的元素的索引，而不是基准本身的索引。
为了保持与原问题及修正思路的一致性，我们继续优化最初的 Lomuto 分区方案。上述修正后的代码中的 partition 方法已经包含了对 left 和 right 指针的正确处理以及基准的最终归位。
关键点与注意事项
- 基准选择：基准的选择对快速排序的性能至关重要。选择不当可能导致最坏情况（O(n^2)），例如每次都选择最大或最小值。随机选择基准或“三数取中法”可以有效避免这种情况。
- 分区实现：分区逻辑是快速排序的核心。确保 left 和 right 指针的移动条件、循环终止条件以及元素交换逻辑的正确性。
- 递归边界条件：正确设置递归的基准情况（即何时停止递归）对于防止无限递归和处理小规模子数组至关重要。
- 处理重复元素：在存在大量重复元素的情况下，原始的快速排序可能会退化。可以修改分区方法，将与基准相等的元素放到中间区域，以提高效率。
- 小数组优化：对于非常小的子数组（例如长度小于10-20），快速排序的递归开销可能高于其他简单排序算法（如插入排序）。在实际应用中，可以考虑当子数组大小达到某个阈值时，切换到插入排序。
总结
通过对一个存在问题的Java快速排序实现进行细致的分析和修正，我们深入理解了递归快速排序算法在分区逻辑、递归边界条件以及基准元素归位等方面的常见陷阱。一个健壮的快速排序实现需要精确控制 left 和 right 指针的移动，确保循环条件的正确性，并在递归调用时进行必要的边界检查。掌握这些关键点，能够帮助开发者构建高效且稳定的快速排序算法。
