c++ - C++ 快速排序无法正常工作

Question

我正在尝试修改一些快速排序代码以将随机数作为枢轴。

但是，在测试程序时，它不能正确排序。我不确定为什么这样做。

int random (int num) {
    int random = rand() % (num - 1);
    return random;
}

int* partition (int* first, int* last);
void quickSort(int* first, int* last) {
    if (last - first <= 1) return;

    int* pivot = partition(first, last);
    quickSort(first, pivot);
    quickSort(pivot + 1, last);
}

int* partition (int* first, int* last) {
    //--int pivot = *(last - 1);    
    int* pos = (first + random(last - first));
    int pivot = *pos;
    int* i = first;
    int* j = last - 1;

    for (;;) {
        while (*i < pivot && i < last) i++;
        while (*j >= pivot && j > first) j--;
        if (i >= j) break;
        swap (*i, *j);
    }
    swap (*pos, *i);
    return i;
}

Answer 1

您的第一个实现有效，但对特定数据集的行为退化。原始工作代码中的枢轴是*(last - 1)最简单的解决方法，就是将随机元素与*(last - 1). 其余的原始分区代码将保持不变。