Java 中的 QuickSort 未提供排序结果

Question

我尝试使用 http://en.wikipedia.org/wiki/Quicksort#Algorithm 中提到的算法实现 QuickSort 的代码。

但是，我无法获得排序后的输出。相反，我只得到与输出相同的数组。

任何人都可以帮我检查并告诉我我的代码有什么问题吗？

public class QuickSort {

private int[] arr;

private void quick_sort(int[] input, int lo, int hi){
    this.arr = input;
    if(lo<hi){
        int p = partition(arr, lo, hi);
        if(lo < p-1)
            quick_sort(arr, lo, p-1);
        if(hi > p+1)
            quick_sort(arr, p+1, hi);
    }
}

private int partition(int[] arr, int lo, int hi){
    int pivotIndex = hi;  //last element
    int pivotVal = arr[pivotIndex];
    int j = lo;

    for(int i = lo; i<hi; i++){
        if(arr[i] < pivotVal){
            swap(arr[j],arr[i]);
            j++;
        }
    }
    swap(arr[j],pivotVal);
    return j;
}

private void swap(int l, int r){
    l = l+r;
    r = l-r;
    l = l-r;
}


private void printArray(){
    for(int i : arr)
        System.out.print(i+", ");
}

public static void main(String[] args) {
    QuickSort q = new QuickSort();
    int[] input = {10, 5, 15, 3, 20, 30, 25, 19};
    q.quick_sort(input, 0, input.length-1);
    q.printArray();
}
};

输出：

10, 5, 15, 3, 20, 30, 25, 19,

Answer 1

您的交换方法不正确。 Java 始终按值传递，不能那样修改原语。相反，传入数组（数组的值，作为 Object 实例，是它的引用）和要交换的索引，如

private void swap(int[] arr, int l, int r) {
    int t = arr[l];
    arr[l] = arr[r];
    arr[r] = t;
}

然后你可以这样称呼它

private int partition(int[] arr, int lo, int hi) {
    int pivotIndex = hi; // last element
    int j = lo;

    for (int i = lo; i < hi; i++) {
        if (arr[i] < arr[pivotIndex]) {
            swap(arr, j, i);
            j++;
        }
    }
    swap(arr, j, pivotIndex);
    return j;
}

输出（仅进行了这些更改）是

3, 5, 10, 15, 19, 20, 25, 30,

此外，您可以像这样打印数组

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

Java 中的 QuickSort 未提供排序结果

QuickSort in Java not delivering sorted results

java

quicksort