c++ - Quicksort 无法一致地对 100 000 个整数的数据集进行排序

Question

我已经用 C++ 实现了 Quicksort 算法的几种变体，但它们都有一个很大的缺陷。他们无法在合理的时间内对 100 000 个整数的数据集进行排序。有时，10000 个整数的数据集也会失败，但频率要低得多。最初，我怀疑是我选择的枢轴导致了这个问题，但即使随机选择了一个枢轴，算法也无法在合理的时间内执行。有人可以帮我找出导致我的 Quicksort 实现性能不佳的原因吗？

下面是我的固定轴快速排序的实现。

void quicksort(std::vector<int> &list, int left, int right)
{
    if (left >= right)
       return;
    int pivot = list[left + (right - left) / 2];
    int oldPivot = partition(list, pivot, left, right);
    quicksort(list, left, oldPivot - 1);
    quicksort(list, oldPivot + 1, right);
}

// Hoare Partitioning Scheme
int partition(std::vector<int> &list, int pivot, int left, int right)
{
    while (true)
    {
        while (list[left] < pivot)
            left++;
        while (list[right] > pivot)
            right--;
        // Stop when the pivot is reached.
        if (left >= right)
            return left;
        std::swap(list[left], list[right]);
    }
}

为了针对包含 100 000 个无序整数的 vector 测试我的快速排序算法，我使用了以下代码:

std::vector<int> randomizeIntVector(int size)
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> rand_int(INT_MIN, INT_MAX);
    std::vector<int> vector;
    for (int i = 0; i < size; i++)
        vector.push_back(rand_int(rng));
    return vector;
}

int main()
{
    std::vector<int> vector = randomizeIntVector(100000);
    std::vector<int> expectedVector = vector;
    quicksort(vector, 0, vector.size() - 1);
    std::sort(expectedVector.begin(), expectedVector.end());
    assert(vector == expectedVector);
}

代码可以针对各种 vector 大小进行测试here

Answer 1

代码中的两个问题:首先，oldPivot 是一个索引而不是一个主元值。该代码将其用作值。将其更改为索引以消除混淆。

其次，对快速排序的调用在 oldPivot 的两边推进，而不是只朝一个方向推进。

此外，在分配随机 vector 时使用预留空间，以便在内部只分配一次内存。

#include <vector>
#include <list>
#include <random>
#include <algorithm>
#include <iostream>


void quicksort(std::vector<int> &list, int left, int right);
int partition(std::vector<int> &list, int pivot, int left, int right);
int randomize_pivot(int left, int right);
std::vector<int> randomizeIntVector(int size);

void print_vector(std::vector<int> v, int left, int right)
{
    for (int i = left; i <= right; i++) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}

void quicksort(std::vector<int> &list, int left, int right)
{

    if (left >= right)
        return;
    int pivot = list[left + (right - left) / 2];
    int index = partition(list, pivot, left, right);
    quicksort(list, left, index - 1);
    quicksort(list, index, right);  // prior was 'index + 1', which skipped a cell
}

// Hoare Partitioning Scheme
int partition(std::vector<int> &list, int pivot, int left, int right)
{
    while (left <= right) {
        while (list[left] < pivot)
            left++;
        while (list[right] > pivot)
            right--;
        if (left <= right) {
            std::swap(list[left], list[right]);
            left++;
            right--;
        }
    }
    return left;
}

std::vector<int> randomizeIntVector(int size)
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> rand_int(INT_MIN, INT_MAX);
    std::vector<int> vector;
    vector.reserve(size);
    for (int i = 0; i < size; i++)
        vector.push_back(rand_int(rng));
    return vector;
}

std::vector<int> smallVector(int size)
{
    std::vector<int> vector1{5, 4, 1, 2, 3};

    return vector1;
}

int main()
{
    std::vector<int> vector = randomizeIntVector(100000);
    std::vector<int> expectedVector = vector;
    quicksort(vector, 0, vector.size() - 1);
    std::sort(expectedVector.begin(), expectedVector.end());

    assert(vector == expectedVector);

}