java - 在 Java 快速排序中使用随机主元

Question

我的代码几乎可以正常工作，给我一个几乎排序的输出数据。 cmp(i,j)方法返回负值if i < j和一个积极的if j > i .

代码:

public void sort(){ 
    sortQuick(0, getElementCount()-1);
}
public void sortQuick (int first, int last){
    // pivot tilldelas ett värde mellan noll och antal element i vektorn.
    final Random random = new Random();
    System.out.println(("Last: " + last + ", first : " + first));
    int up = first;                          
    int down = last; 

    int pivot = random.nextInt(last-first) + first;
    System.out.println(pivot);                          
    while (up < down ) {

        while (cmp(up,pivot) < 0) {
            up++;
        }
        while (cmp(down,pivot) > 0) {
            down--;
        }
        if (up <= down) {
            swap(up,down);
            up++;
            down--;
        }
    }
    if (down > first) {
        sortQuick(first, down);
    }
    if (last > up) {
        sortQuick(up, last);
    }
}

建议？

Answer 1

问题是您只存储枢轴元素的索引，而不存储实际值。

如果在算法的后面，up(或down)碰巧达到值pivot并进行交换，则索引pivot处的值会发生变化。因此，后续比较是针对不同的主元元素。

记住主元值并对其进行所有比较，如下所示:

int pivotIndex = random.nextInt(last-first) + first;
int pivotValue = getValueAt(pivotIndex);

while (up < down ) {

    while (getValueAt(up) < pivotValue) {
        up++;
    }
    while (getValueAt(down) > pivotValue) {
        down--;
    }
    if (up <= down) {
        swap(up,down);
        up++;
        down--;
    }

或者，您可以在交换时更新枢轴索引:

    if (up <= down) {
        swap(up,down);
        if(pivot == up) { pivot = down; }
        else if(pivot == down) { pivot = up; }
        up++;
        down--;
    }