Java递归快速排序算法的优化与常见错误修正-java教程-PHP中文网

Java递归快速排序算法的优化与常见错误修正

本文深入探讨了Java中递归快速排序算法的常见实现问题，重点分析了分区（partition）逻辑和递归边界条件处理不当导致的排序错误。通过详细的代码示例和逐步解析，文章提供了针对性的修正方案，包括优化基准元素（pivot）放置、调整递归调用条件以及确保分区循环的健壮性，旨在帮助开发者构建一个正确且高效的快速排序实现。

快速排序算法概述

快速排序（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：

法语写作助手
法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

31

查看详情
- 在 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 小于某个阈值时，切换到插入排序。
避免最坏情况：
- 最坏情况通常发生在基准元素总是最大或最小的情况下。随机选择基准或三数取中法可以有效缓解这个问题。
重复元素处理：
- 当数组中存在大量重复元素时，标准的快速排序性能可能会下降。一种改进是“三向切分快速排序”，它将数组分为三部分：小于基准、等于基准和大于基准，从而提高处理重复元素的效率。