Java中的递归Quicksort的分区实现不起作用

问题描述

写了这个递归快速排序算法的Java实现，并且似乎出错了，因为我尝试排序的数组几乎完全排序，除了应该切换的两个元素（靠近数组的中间）。我想要排序的整数数组是：4,77,98,30,20,50,77,22,49,2（10个元素）。这是我的代码：

Wrote this Java implementation of a recursive quicksort algorithm, and something seems to go awry as the array I am trying to sort almost sorts perfectly except for two elements that should be switched (near the middle of the array). The array of integers I am trying to sort is: 4, 77, 98, 30, 20, 50, 77, 22, 49, 2 (10 elements). Here is my code:

public static void quickSort(int[] array, int start, int end) {
    if (start < end) {
        int partition = partition(array, start, end);
        quickSort(array, start, partition - 1);
        quickSort(array, partition + 1, end);
    }
}

public static int partition(int[] array, int left, int right) {
    int pivotValue = array[(left + right) / 2]; //Value of middle element in array
    while (left <= right) {
        while (array[left] < pivotValue) {
            left++;
        }
        while (array[right] > pivotValue) {
            right++;
        }
        if (left <= right) {
            /* swap code */
            int temporary = array[left]
            array[left] = array[right]
            array[right] = temporary;

            left++;
            right--;
        }
    }
    return left;
}

当我尝试使用此算法时：

When I try this algorithm out with:

int[] array = {4, 77, 98, 30, 20, 50, 77, 22, 49, 2};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
}

打印出来：
2,4,20， 30,22 ，49,50,77,77,98

It prints out:2, 4, 20, 30, 22, 49, 50, 77, 77, 98

任何帮助弄清楚为什么这两个元素没有正确排序的任何帮助都将受到高度赞赏。我确信这是我在编写分区代码时遗漏的东西。谢谢！

Any help figuring out why those two elements aren't correctly sorted would be highly appreciated. I'm sure it's something I missed while writing the partition code. Thanks!

推荐答案

问题是你要留下1个要检查的元素

只需要替换你的代码：

The problem is that you are leaving 1 element to be checked
just replace your code :

quickSort(array, start, partition - 1);
quickSort(array, partition + 1, end);

这个：

quickSort(array, start, partition - 1);
quickSort(array, partition, end);

或用此：

quickSort(array, start, partition);
quickSort(array, partition + 1, end);

我假设现在原因很清楚，但请告诉我你是否需要一些解释。

I am assuming that the reason is clear now, but tell me if you need some explanation.

这篇关于Java中的递归Quicksort的分区实现不起作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！