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

Question

在我的macOS的Xcode中，我对quicksort.when做了一个计时器测试，我的元素的数量大约是10，100。直到我设置了1000这样的数量，我的就地版本的运行时间才会比另一个版本慢。我使用C++来做这个测试。下面是我的main函数的代码：

    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;
}

自从我设置了类似1，000，10000等的数量，就地就开始变慢了。例如，当数量等于1000时，在位版本花费0.005356秒，但普通版本使用0.001464秒。当数量达到100k时，就地版本大约是50秒，而正常版本大约是0.5秒。有人能告诉我为什么吗？

抱歉有任何语法错误，英语不是我的母语。

Answer 1

无可奉告，但在原地版本中，您不需要lambda，也不需要返回向量。未经测试，只需对原始代码进行最小程度的更改：

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);
}