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

Question

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

代码返回了以下古怪的值。

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

Answer 1

quicksort 方法应该有一个 if 而不是 while。我还没有检查其余代码，但那部分肯定是错误的。递归调用应该已经确保您继续进行直到它被排序，不需要额外的循环。

Answer 2

您代码中最大的问题位于 partition 方法的底部：

int rval = arr[r];
int i1val = arr[i + 1];
arr[r] = i1val;
arr[i] = rval; // <-- here

您将 i1val 设置为 arr[i + 1]，但随后您将 arr[i] 设置为 rval，而不是将 arr[i + 1] 设置为 rval .

修复此问题以及中提到的数组长度问题应该会修复您的代码。

Answer 3

我可以看到三个问题-

数组的长度是 13，但是你传递的是 11 作为结束索引（应该是 12）
更重要的是，分区函数末尾的swap有问题。应该是arr[i+1] = rval，而不是arr[i] = rval.
您不需要 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;
}

编辑：原来在我写这篇文章时其他答案中都指出了所有这些。不过我想把答案留在这里也没什么坏处。

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

My Quick Sort implementation in Java is sorting only part of the array. Not sure why it's doing this

java

sorting

algorithm

quicksort