java - QuickSort后如何打印排序的数组

我已经写了一个快速排序算法，我相信是正确的。我只想打印出排序好的数组，但我似乎想不通。我的算法是：

public static void quickSort(int[] myArray, int left, int right) {

    if(left < right) {
        int s = hoarePartition(myArray, left, right);
        quickSort(myArray, left, s-1);
        quickSort(myArray, s+1, right);
    }


public static int hoarePartition(int[] myArray, int left, int right) {

    int p = myArray[left];
    int i = left;
    int j = right;

    while(i < j) {
        while(myArray[i] < p) {
            i++;
        }
        while(myArray[j] > p) {
            j--;
        }
        int temp = myArray[i];
        myArray[i] = myArray[j];
        myArray[j] = temp;
    }

    int temp = myArray[left];
    myArray[left] = myArray[j];
    myArray[j] = temp;
    return j;
}

分区正在返回正确的结果我的主调是：

        int[] myArray= {3,2,1};
        System.out.println(Arrays.toString(myArray));
        QuickSort(myArray, 0, myArray.length-1);
        System.out.println(Arrays.toString(myArray));

我得到[3,2,1]和[3,2,1]作为输出我正在寻找排序后的[1,2,3]作为第二个输出我完全错过了什么吗？我觉得这应该很容易。。。
提前谢谢！

最佳答案

这段代码中有一个bug：

while(i < j) {
    while(A[i] < p) {
        i++;
    }
    while(A[j] > p) {
        j--;
    }
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

注意，在外部循环的第一次迭代中，您交换第一个和最后一个元素，并获得（如预期的那样）：

A = [3, 2, 1]

在第一次迭代中，i,j没有改变。
但是在第二次迭代中会发生什么呢？

while (A[i] < p) { i++; }

只有当i==2和A[i] == 3
同样，对于

while(A[j] > p) { j--;  }

你最终会有j == 0和A[j] = 1
现在，你交换它们-不管j < i
一个快速的解决方法是在交换元素之前对i < j进行健全性检查，因为在i和j上的两个循环之后，不再保证外部循环属性为true。
另外请注意，如果数组可以包含重复项，则代码将进入无限循环，例如-尝试对数组进行排序-它将无休止地交换这两个

关于java - QuickSort后如何打印排序的数组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28850571/