# algorithm - 为什么就地QuickSort比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;
}
``````

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

varrtix

94
user11729096 2019-07-03 21:45

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

``````