C++ vectors Quicksort - 似乎对不同的枢轴有不同的工作方式

Question

当我将枢轴作为第一个、最后一个或中间元素而不是其他一些值时，我使用 C++ 向量的快速排序算法似乎工作正常。

我不确定所有这些，但是例如，如果我将基准设置为 (r-l)/2，它将无法正确排序。

我相信我的代码是正确的，但我不确定；可能存在严重错误。

是否有可能有时工作有时不工作，这取决于支点？

我以为它只影响了运行时间，所以我猜我的代码有问题。

以下是我的代码：

#include <vector>
#include <algorithm>

using namespace std;

int choosePivot(int l, int r) {
    return (r-l)/2; // or Even r/2
}

int partition(vector<int>& vec, int l, int r) {
    int pi = choosePivot(l, r); // pivot index
    int pivot = vec[pi];

    // swap pivot with the beginning
    swap(vec[pi], vec[l]); 

    // beginning index of the right side of the pivot (larger than the pivot)
    int i = l + 1;

    // partition around the pivot
    for (int j = l+1; j <= r; ++j) {
        if (vec[j] <= pivot) {
            swap(vec[i], vec[j]);
            ++i;
        }
    }

    // swap pivot back to its position
    swap(vec[l], vec[i - 1]);

    // return pivot position
    return i - 1;
}

void quicksort(vector<int>& vec, int l, int r) {
    if (l < r) {
        int p = partition(vec, l, r);
        quicksort(vec, l, p - 1);
        quicksort(vec, p + 1, r);
    }
}

int main() {

    ifstream infile("IntegerArray.txt"); 
    int a;
    vector<int> vec;
    vec.reserve(100000);
    while (infile >> a)
        vec.push_back(a);

    quicksort(vec, 0, vec.size() - 1);

    return 0;
}

我添加了一个测试示例的主函数。

这是IntegerArray.txt

这是一个包含从 1 到 100,000（没有重复）的所有整数的文件。

我编辑了 choosePivot 函数，它会输出错误排序的数组。

我没有印刷品，因为尺寸太大了。

Answer 1

上面代码中实现快速排序的方式，当枢轴索引不在l和r之间时它会中断。在这种情况下，它首先从带有 swap(vec[pi], vec[l]); 的 [l, r] 段之外引入一个值。这可能会破坏数组的 already-sorted 部分。

现在，(r-l)/2 并不总是在 l 和 r 之间。例如，当 l = 10 和 r = 20 时，主元索引为 (20-10)/2 = 5。因此，代码将通过交换 vec[5] 和 vec[10] 开始对 [10, 20] 段进行排序。如果 vec[5] 的部分排在 [10, 20] 段之前，这很可能导致数组最后没有被排序。

C++ vectors Quicksort - 似乎对不同的枢轴有不同的工作方式

C++ vectors Quicksort - Seems to work differently with different pivots

c++

algorithm

quicksort