快速排序算法概述
快速排序（quicksort）是一种高效的、基于比较的排序算法，其核心思想是“分治法”（divide and conquer）。它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终使整个数据序列有序。
快速排序的基本步骤如下：
- 选择基准元素（Pivot）：从数组中选择一个元素作为基准。
- 分区（Partition）：重新排列数组，将所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边。在分区结束后，基准元素会处于其最终的排序位置。
- 递归排序：对基准元素左边和右边的两个子数组分别递归地执行快速排序。
常见实现问题与错误分析
在实现快速排序时，尤其是在处理递归边界和分区逻辑时，很容易引入细微的错误，导致排序结果不正确或程序崩溃。以下是一个常见的、存在问题的快速排序实现示例：
public class QuickSortOriginal {
public static void quickSort(int[] s) {
quickSortSub(s, 0, s.length - 1);
}
private static void quickSortSub(int[] s, int a, int b) {
// 原始条件：如果子数组长度大于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) {
while(s[left] < pivot) {
left++;
}
while(s[right] > pivot) {
right--;
}
if(left < right) {
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
// 基准元素放置
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("");
}
}上述代码在某些情况下能够正常工作，但在面对特定输入时会产生不正确的排序结果。其主要问题点在于：
-
quickSortSub 中的递归终止条件：
立即学习“Java免费学习笔记（深入）”；
- 原始条件 if(b-a > 1) 意味着当子数组只包含一个元素或两个元素时，递归会停止。然而，对于 b-a == 1（即两个元素），例如 [10, 5]，partition 可能会正确地将它们排序为 [5, 10]，但 quickSortSub 不会对其进行处理，导致可能未排序。更重要的是，如果 partition 返回的 point 使得 point - 1 或 point + 1 超出了有效范围，或者形成空数组（例如 point - 1 < a），则可能导致无限递归或数组越界。
-
partition 方法中的 while 循环条件：
- while(left < right) 确保了 left 和 right 指针在交叉前进行交换。然而，内部的 while(s[left] < pivot) 和 while(s[right] > pivot) 循环可能在 left 或 right 指针移动到 a 或 b 的边界时，没有充分考虑。特别是 right 指针，如果 s[right] 一直大于 pivot，right 会一直递减，可能在 right == a 时，如果 s[a] 仍然大于 pivot，right 会继续递减到 a-1，导致数组越界或逻辑错误。
-
基准元素 pivot 的最终放置：
- 在 partition 方法的最后，s[b] = s[left]; s[left] = pivot; 这行代码旨在将基准元素放置到其最终位置。然而，如果 left 指向的元素 s[left] 实际上小于 pivot（例如，当 left 最终停留在 pivot 的左侧），或者 left 已经越界，这个交换可能会导致 pivot 被放置到错误的位置，或者将一个不应移动的元素与 pivot 交换。
优化与修正方案
针对上述问题，我们可以对快速排序算法进行如下优化和修正：
-
调整 quickSortSub 的递归终止条件：
- 将 if(b-a > 1) 改为 if(b-a >= 1) 或 if (a < b)。a < b 是更通用的条件，表示子数组至少包含两个元素。如果只有一个元素，a == b，则无需排序。
- 在递归调用子数组前，增加对子数组有效性的检查。例如，quickSortSub(s, a, point - 1) 之前，应确保 a < point - 1。
-
增强 partition 方法的健壮性：
- 在主 while(left < right) 循环中，确保 right 指针不会越过 a。即 while(left < right && right > a)。这可以防止 right 指针在极端情况下（例如，所有元素都大于 pivot）递减到 a 以下。
- 在内部 while 循环中，也应考虑边界条件，例如 while(left < right && s[left] < pivot) 和 while(left < right && s[right] > pivot)。
-
精确放置基准元素 pivot：
- 在 partition 方法的最后，将 pivot 放置到 left 指针最终停留的位置。这个位置应该是所有小于 pivot 的元素之后、所有大于 pivot 的元素之前。修正后的逻辑应确保 s[left] 处的元素大于或等于 pivot 时才进行交换，这保证了 pivot 被放置到正确的位置。
以下是修正后的快速排序实现代码：
public class QuickSort {
public static void quickSort(int[] s) {
if (s == null || s.length == 0) {
return;
}
quickSortSub(s, 0, s.length - 1);
}
private static void quickSortSub(int[] s, int a, int b) {
// 修正1: 当子数组至少包含两个元素时才进行分区
if (a < b) {
int point = partition(s, a, b);
// 修正2: 递归调用前检查子数组的有效性
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) { // 修正3: left <= right 确保所有元素被检查
// 修正4: 确保left指针不会越界且找到大于等于pivot的元素
while (left <= right && s[left] < pivot) {
left++;
}
// 修正5: 确保right指针不会越界且找到小于等于pivot的元素
while (left <= right && s[right] > pivot) {
right--;
}
if (left <= right) { // 修正6: 只有当left和right未交叉时才交换
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
// 修正7: 将基准元素放到正确的位置
// 此时left指针指向第一个大于或等于pivot的元素，或者已经越过right
// 我们需要将pivot（原s[b]）与s[left]交换
// 实际上，更常见的partition实现是将pivot与right+1位置的元素交换，
// 或者在循环结束后将pivot放到left和right交叉点的位置。
// 下面提供一种更标准且健壮的Hoare分区或Lomuto分区变体
// 考虑原始问题中的partition逻辑，它将pivot放在s[b]
// 并在最后与s[left]交换。为了兼容原始逻辑并修正，
// 我们可以将pivot与最终left指针指向的元素交换，
// 确保left指向的元素是第一个大于或等于pivot的元素。
// 这里的left就是pivot的最终位置。
// 以下是基于Lomuto分区方案的改进，它通常更易于理解和实现：
// 我们可以将pivot先与s[b]交换，然后将s[b]作为pivot。
// 或者，将s[b]作为pivot，然后将它移动到正确的位置。
// 针对原代码的修正，pivot的最终位置是left。
// 原始代码的最后交换逻辑：
// s[b] = s[left];
// s[left] = pivot;
// return left;
// 修正后的逻辑：将基准元素（原始s[b]）放置到left指针的最终位置
// 此时left指针停在第一个大于或等于pivot的元素位置
// 如果pivot是s[b]，那么在循环结束后，left指向的元素就是pivot应该在的位置
// 或者，我们也可以在partition开始时就将pivot交换到a，或者随机选择。
// 为了与原代码保持一致，基准元素是s[b]。
// 循环结束后，left指向第一个大于等于pivot的元素，right指向第一个小于等于pivot的元素。
// 如果我们用s[b]作为pivot，那么left就是pivot的最终位置。
// 确保s[left] >= pivot，然后交换s[b]和s[left]。
// 考虑到原始答案的修正，它在最后做了条件判断交换。
// 我们可以直接将pivot（原s[b]）与s[left]交换，因为在循环结束后，
// left指向的元素是第一个大于等于pivot的，或者left已经越过了right。
// 此时left就是pivot的最终位置。
int pivotFinalPos = left; // pivot的最终位置
int temp = s[pivotFinalPos];
s[pivotFinalPos] = s[b]; // 将pivot（原始s[b]）放到pivotFinalPos
s[b] = temp; // 将pivotFinalPos的原始值放回b
return pivotFinalPos;
}
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);
System.out.print("Sorted array: ");
for (int i: arr) System.out.print(i + ", ");
System.out.println("");
int[] arr2 = {5, 2, 8, 1, 9, 4};
quickSort(arr2);
System.out.print("Sorted array2: ");
for (int i: arr2) System.out.print(i + ", ");
System.out.println("");
int[] arr3 = {10, 5};
quickSort(arr3);
System.out.print("Sorted array3: ");
for (int i: arr3) System.out.print(i + ", ");
System.out.println("");
int[] arr4 = {1};
quickSort(arr4);
System.out.print("Sorted array4: ");
for (int i: arr4) System.out.print(i + ", ");
System.out.println("");
}
}对上述修正的详细解释：
-
quickSortSub(int[] s, int a, int b) 方法：
- if (a < b): 这是更准确的递归终止条件。当 a 等于 b 时，子数组只有一个元素，自然有序，无需再排序。当 a 大于 b 时，子数组为空，也无需处理。这比 b-a >= 1 更直观且涵盖了所有有效情况。
- 注意：在原始答案中，quickSortSub 内部增加了 if(point>=a+2) 这样的条件。这通常是为了处理 partition 结果导致某个子数组为空或只有一个元素的情况，以避免不必要的递归调用或潜在的栈溢出。然而，如果 partition 逻辑正确，并且递归条件是 a < b，则通常不需要额外的 point>=a+2 检查。我的修正方案中，partition 确保 left 返回的是基准的最终位置，quickSortSub 递归调用 a, point-1 和 point+1, b，只要 a < point-1 和 point+1 < b 成立，递归就会继续。当子数组只有一个元素或为空时，a < b 条件会阻止进一步递归。
-
partition(int[] s, int a, int b) 方法：
- int pivot = s[b];: 仍然选择最右侧元素作为基准。
- while (left <= right): 这是Hoare分区方案的常见循环条件，它允许 left 和 right 指针在交叉前进行交换。
- while (left <= right && s[left] < pivot) 和 while (left <= right && s[right] > pivot): 内部循环增加了 left <= right 的条件，确保指针不会越界，并且在找到合适元素之前持续移动。
- if (left <= right): 在执行交换前，再次检查 left <= right，防止指针交叉后仍尝试交换。交换后，left 和 right 各自向内移动一步。
- 基准元素放置：在 while 循环结束后，left 指针会停在第一个大于或等于 pivot 的元素位置，right 指针会停在第一个小于或等于 pivot 的元素位置。此时 left 就是 pivot 最终应该放置的位置。因此，将 s[b] (原始的 pivot 值) 与 s[left] 交换，并将 left 作为 pivot 的最终位置返回。
另一种更简洁的Lomuto分区方案
上述修正方案在一定程度上是基于原始代码逻辑的优化。在实际开发中，Lomuto分区方案因其简洁性而广受欢迎，虽然在处理重复元素时效率可能略低于Hoare分区。以下是基于Lomuto分区思想的修正版本：
public class QuickSortLomuto {
public static void quickSort(int[] s) {
if (s == null || s.length == 0) {
return;
}
quickSortSub(s, 0, s.length - 1);
}
private static void quickSortSub(int[] s, int a, int b) {
if (a < b) {
int pivotIndex = partition(s, a, b);
quickSortSub(s, a, pivotIndex - 1);
quickSortSub(s, pivotIndex + 1, b);
}
}
private static int partition(int[] s, int a, int b) {
int pivot = s[b]; // 选择最右侧元素作为基准
int i = a - 1; // i 指向小于pivot区域的最后一个元素
for (int j = a; j < b; j++) {
if (s[j] <= pivot) { // 如果当前元素小于或等于基准
i++;
// 交换 s[i] 和 s[j]
int temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
// 将基准元素放到正确的位置
// 此时 i+1 是第一个大于pivot的元素的位置
int temp = s[i + 1];
s[i + 1] = s[b];
s[b] = temp;
return i + 1; // 返回基准元素的最终索引
}
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);
System.out.print("Sorted array (Lomuto): ");
for (int i: arr) System.out.print(i + ", ");
System.out.println("");
}
}注意事项与最佳实践
-
基准元素选择策略：
- 固定选择：如上述示例选择最右侧元素。简单但容易导致最坏情况（O(n^2)）性能，当数组已部分排序或逆序时。
- 随机选择：从子数组中随机选择一个元素作为基准，然后将其与 s[b] 交换。这大大降低了遇到最坏情况的概率。
- 三数取中法：选择子数组的第一个、中间和最后一个元素，取它们的中位数作为基准。这通常能更好地选择一个接近中值的基准，提高性能。
-
处理小数组：
- 对于非常小的子数组（例如，长度小于10-20），快速排序的递归开销可能大于其他简单排序算法（如插入排序）。在这种情况下，可以考虑在 quickSortSub 中增加一个条件，当 b - a 小于某个阈值时，切换到插入排序。
-
避免最坏情况：
- 最坏情况通常发生在基准元素总是最大或最小的情况下。随机选择基准或三数取中法可以有效缓解这个问题。
-
重复元素处理：
- 当数组中存在大量重复元素时，标准的快速排序性能可能会下降。一种改进是“三向切分快速排序”，它将数组分为三部分：小于基准、等于基准和大于基准，从而提高处理重复元素的效率。
总结
快速排序算法的正确实现对边界条件和分区逻辑的精确把握有着严格要求。通过对递归终止条件、分区循环条件以及基准元素放置逻辑的细致审查和修正，我们可以构建一个健壮且高效的快速排序算法。理解并应用这些修正方案，不仅能解决排序错误，还能加深对分治算法和指针操作的理解，为处理更复杂的算法问题打下坚实基础。
