# 快排(quick sort) C++ 实现

··1231 words·3 mins·
Programming Sorting

# 非原地算法#

``````#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <ctime>

using std::random_device;
using std::cout;
using std::endl;
using std::vector;
using std::string;

void printList(vector<int>&, const string&);

vector<int> quickSort(vector<int> arr){
if (arr.size() <= 1){
return arr;
}

int N = arr.size();
// arr[mid] 是 pivot
int mid = (N-1) / 2;

vector<int> left;
vector<int> right;

for (int i = 0; i < N; i++){
if (i == mid) continue;

// 对于原始数组，小于等于 pivot 的元素放左子数组，大于 pivot 的元素放右子数组
if (arr[i] <= arr[mid]){
left.push_back(arr[i]);
}
else{
right.push_back(arr[i]);
}
}

// 对左右子数组，再分别进行快排
left = quickSort(left);
right = quickSort(right);

vector<int> new_arr;
for (auto & x: left){
new_arr.push_back(x);
}
new_arr.push_back(arr[mid]);
for (auto & x: right){
new_arr.push_back(x);
}

return new_arr;
}

// Generate a random sequence of length len, in range(low, high) (inclusive).
// need to #include<random>
vector<int> genRandom(int low, int high, int len){
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> distribution(low, high);

vector<int> arr(len, 0);
for (int i = 0; i != len; ++i){
arr[i] = distribution(gen);
}

return arr;
}

void printList(vector<int>& arr, const string& desc){
cout << desc << ": ";

for (auto it = arr.begin(); it != arr.end(); it++){
cout << *it << ((it != arr.end()-1) ? ' ' : '\n');
}
}

int main()
{
vector<int> arr = genRandom(1, 1000, 10);
cout << "Before quick sort\n";
printList(arr, "arr");

auto arr1 = quickSort(arr);
cout << "After quick sort\n";
printList(arr1, "arr1");

return 0;
}
``````

# 原地算法#

``````#include <iostream>
#include <vector>
#include <random>

using namespace std;

// Generate a random sequence of length len, in range(low, high) (inclusive).
// need to #include<random>
vector<int> genRandom(int low, int high, int len){
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> distribution(low, high);

vector<int> arr(len, 0);
for (int i = 0; i != len; ++i){
arr[i] = distribution(gen);
}

return arr;
}

int partion(vector<int> &arr, int low, int high) {
int pivot = arr[low];
int i = low;

for (int j = low+1; j < high; j++){
if (arr[j] <= pivot){
i++;
swap(arr[i], arr[j]);
}
}
// 经过上述 for 循环， i 以及 i 左边都是小于等于 pivot 的元素，最后把 arr[i] 和
// pivot 元素位置调换一下即可。即可保证我们完成了 partion
swap(arr[i], arr[low]);

return i;
}
void quickSort(vector<int>& arr, int low, int high){
// low < high，才需要排序
if (low < high){
int r = partion(arr, low, high);

quickSort(arr, low, r);
quickSort(arr, r+1, high);
}
}

int main() {
vector<int> arr = genRandom(1, 100, 5);

for(auto e: arr)
cout<< e <<" ";
cout<< endl;

int N = arr.size();
quickSort(arr, 0, N);

for(auto e: arr)
cout<< e <<" ";
cout<< endl;

return 0;
}
``````

# 参考#

## Related

··1796 words·4 mins
Programming Algorithms Sorting
When Does the Stability of Sorting Algorithms Matter?
··362 words·2 mins
Programming Algorithms Sorting

··1329 words·3 mins
Programming C++ Algorithms Search