c++ - 为什么 In-place QuickSort 比 C++ 中的普通版本慢？

Question

在我的 macOS 的 Xcode 中，我为快速排序做了一个计时器测试。当我的元素数量像 10、100 时。在我设置像 1000 这样的数量之前，我的就地版本的运行时间变得比另一个版本。我正在使用 C++ 来做这个测试。这是我的主要功能的代码:

    const int sort_size = 100000;
    clock_t begin, end;
    vector<int> vec_1;
    srand((unsigned)time(NULL));
    for (auto i = 0; i < sort_size; ++i) {
        auto r = rand() % sort_size;
        vec_1.push_back(r);
    }
    vector<int> vec_2(vec_1);
    begin = clock();
    auto sort_1 = QuickSort::exec(vec_1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);
    begin = clock();
    auto sort_2 = QuickSort::exec_in_place(vec_2, 0, sort_size - 1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);

这两个函数都使用了静态声明。

这是就地版本代码:

vector<int> QuickSort::exec_in_place(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return nums;
    }
    auto pivot = [=, &nums] () {
        auto pivot_idx = begin + (end - begin) / 2;
        auto pivot_val = nums[pivot_idx], idx_1 = begin;
        std::swap(nums[pivot_idx], nums[end]);
        for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
            if (nums[idx_2] > pivot_val) continue;
            std::swap(nums[idx_1], nums[idx_2]);
            idx_1++;
        }
        std::swap(nums[idx_1], nums[end]);
        return idx_1;
    }();
    exec_in_place(nums, begin, pivot - 1);
    exec_in_place(nums, pivot + 1, end);
    return nums;
}

我试过把lambda函数拉出来打包成另一个静态函数，结果还是一样。

这是我的另一个普通版本，它也是使用递归风格。

vector<int> QuickSort::exec(const vector<int> &nums) {
    if (nums.size() < 2) {
        return nums;
    }
    auto pivot = nums[0];
    vector<int> smaller;
    vector<int> greater;
    for (auto i = 1; i < nums.size(); ++i) {
        int num = nums.at(i);
        if (num < pivot) {
            smaller.push_back(num);
        } else {
            greater.push_back(num);
        }
    }
    auto smaller_nums = exec(smaller);
    auto greater_nums = exec(greater);
    smaller_nums.push_back(pivot);
    smaller_nums.insert(smaller_nums.end(), greater_nums.begin(), 
    greater_nums.end());
    return smaller_nums;
}

自从我将数量设置为 1000、10000 等之后，In-place 开始变慢。例如，当数量等于1000时，In-place花费了0.005356sec，而普通版本使用了0.001464sec。当数量达到100k左右时，In-place版本约为50sec，而普通版本约为0.5sec。谁能告诉我为什么？

对于任何语法错误，我深表歉意，英语不是我的母语。

Answer 1

无法评论，但在就地版本中，您不需要 lambda，也不需要返回 vector 。未经测试，对原始代码的改动很小:

void exec_in_placex(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return;
    }

    auto pivot_idx = begin + (end - begin) / 2;
    auto pivot_val = nums[pivot_idx], idx_1 = begin;
    std::swap(nums[pivot_idx], nums[end]);
    for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
        if (nums[idx_2] > pivot_val) continue;
        std::swap(nums[idx_1], nums[idx_2]);
        idx_1++;
    }
    std::swap(nums[idx_1], nums[end]);
    auto pivot = idx_1;

    exec_in_placex(nums, begin, pivot - 1);
    exec_in_placex(nums, pivot + 1, end);
}