时间戳

首页 > 解决方案 > QuickSort 的枢轴选择，发生了什么，我的算法中有什么不正确的吗？

java - QuickSort 的枢轴选择，发生了什么，我的算法中有什么不正确的吗？

问题描述

有人可以指导我实施 QuickSort。当我选择枢轴作为数组中的最后一个元素时，我试图想象我的快速排序实现有什么问题。

下面是我的代码：

    public void quickSort(int[] input, int left, int right) {
        if(left < right) {
            //int pivot = input[(left + right) / 2]; // works fine with this
            //int pivot = input[left];               // works fine with this
            int pivot = input[right];
            int index = partition(input, left, right, pivot); // line 12
            quickSort(input, left, index - 1); // line 13
            quickSort(input, index, right);    // line 14
        } 
    }
    
    private int partition(int[] input, int left, int right, int pivot) {
        while(left <= right) {
            while(input[left] < pivot) {
                left++;
            }
            while(input[right] > pivot) {
                right--;
            }
            if(left <= right) {
                int temp = input[left];
                input[left] = input[right];
                input[right] = temp;
                left++;
                right--;
            }
        }
        return left;
    }

如果当我选择枢轴时工作正常

int pivot = input[(left + right) / 2]; // works with this
int pivot = input[left + (right - left) / 2]; // works with this
int pivot = input[left];               // works with this

当 pivot 是input[right]时，它会失败，除了

Exception in thread "main" java.lang.StackOverflowError
    at com.maverick.solution.Solution.quickSort(Solution.java:12)
    at com.maverick.solution.Solution.quickSort(Solution.java:13)

请指导我，纠正问题或出了什么问题。

谢谢 ！

标签： javaalgorithmsortingquicksort

解决方案

问题基本上出现在最大元素到达数组末尾时。在这种情况下，left值right将相等partition()并将返回array.length+1，并且将一次又一次地进行相同的函数调用。

示例：[5,4,3,2,1] 如果您调试代码，您将看到问题在quickSort([1,4,3,2,5],1,4)调用发生时开始。这个调用partition()返回 5 并在下一行再次quickSort([1,4,3,2,5],1,4)发生，循环继续。

partition()当left和right值变得相等并且最大元素出现在right位置时，可能需要对逻辑进行更正。

想想 的工作partition()，基本上是返回索引直到哪个数组被排序，你的逻辑是partition()实现它吗？

尝试不同的输入并调试代码。

有关快速排序的更多信息，您可以参考这本书

推荐阅读