java - 我在 Java 中的快速排序实现仅对数组的一部分进行排序。不确定为什么要这样做

Question

我写了一些代码来学习java中的快速排序算法。我相信这应该按照我的方式工作，但我在这里是因为整个数组没有正确排序。我已经对此进行了多次审查，但没有任何运气。提前感谢您对我的代码提供的任何见解。

代码返回以下古怪的值。

[9, 105, 45, 1, 19, 125, 125, 125, 125, 125, 1852, 1852, 180]

Answer 1

我可以看到三个问题-

1. 数组的长度是 13，但你传递的是 11 作为结束索引(应该是 12)
2. 更重要的是，分区函数末尾的交换存在问题。应该是arr[i+1] = rval，而不是arr[i] = rval。
3. 您不需要 while 循环，也不需要增加和减少开始和结束索引。

更正后的代码是-

public static void main(String[] args) {
    int[] arr = { 9, 105, 45, 1, 19, 1852, 3, 0, 66, 9, 2,125, 180 };
    quickSort(arr, 0, 12);

    System.out.println(Arrays.toString(arr));
}

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

public static int partition(int [] arr, int p, int r){
    int x = arr[r];
    int i = p - 1;
    for(int j = p; j <= r-1; j++){
        if(arr[j] <= x){
            i++;
            int ival = arr[i];
            int jval = arr[j];
            arr[i] = jval;
            arr[j] = ival;

        }
    }
    int rval = arr[r];
    int i1val = arr[i + 1];
    arr[r] = i1val;
    arr[i+1] = rval;
    return i + 1;
}

编辑:事实证明，在我写这篇文章时，所有这些都在其他答案中指出了。不过，我想把答案留在这里也没什么坏处。