当枢轴不是第一个元素时计算比较

Question

我已经尝试实现快速排序算法，但不同的枢轴似乎不起作用。当枢轴元素不是第一个元素时，它总是以递归循环结束，导致崩溃，其中变量 i 从数组中消失，它再次使用完整数组调用自身，但没有任何变化。我认为错误是比较 toSort[j] 与枢轴值，或与其他元素交换后的第一个元素。

public static void quickSort(int[] toSort, int l, int r){
    if(r - l <= 1)return;
    counter += r - l - 1;
    int p = choosePivot(l, r);
    int pivot = toSort[p];
    int oldP = toSort[p];
    toSort[p] = toSort[l];
    toSort[l] = oldP;

    int i = l + 1;
    for(int j = l + 1; j < r; j++){
        if(toSort[j] < pivot){
            int swap = toSort[j];
            toSort[j] = toSort[i];
            toSort[i] = swap;
            i++;
        }
    }


    oldP = toSort[i - 1];
    toSort[i - 1] = toSort[l];
    toSort[l] = oldP;

    quickSort(toSort, l, i);
    quickSort(toSort, i, r);
}

public static int choosePivot(int m, int n){
    return n - 1;
    //return m;
}

Answer 1

问题是对 quickSort() 的递归调用没有收敛。最后两行的轻微变化将像魔术一样起作用。

public static void quickSort(int[] toSort, int l, int r){
    if(r - l <= 1)return;
    counter += r - l - 1;
    int p = choosePivot(l, r);
    int pivot = toSort[p];
    int oldP = toSort[p];
    toSort[p] = toSort[l];
    toSort[l] = oldP;

    int i = l + 1;
    for(int j = l + 1; j < r; j++){
        if(toSort[j] < pivot){
            int swap = toSort[j];
            toSort[j] = toSort[i];
            toSort[i] = swap;
            i++;
        }
    }


    oldP = toSort[i - 1];
    toSort[i - 1] = toSort[l];
    toSort[l] = oldP;

    quickSort(toSort, l, i-1);
    quickSort(toSort, i, r);
}

public static int choosePivot(int m, int n){
    return n - 1;
    //return m;
}

您可以查看 Ideone link 以获取更新的代码。

当枢轴不是第一个元素时计算比较

Counting Comparisons When The Pivot Is Not The First Element

java

sorting

algorithm

quicksort