QuickSort 快速排序是常见的考察代码基本功面试题。简洁易读的实现可以一定程度展现面试者的代码功底。

# 快排框架

void qsort(vector<int> &v, int begin, int end)
{
if (begin >= end) return;
int p = partition(v, begin, end);
qsort(v, begin, p - 1);
qsort(v, p + 1, end);
}

# partition算法实现

## 单边扫描

int partition(vector<int> &v, int begin, int end)
{
int pivot = v[end], i = begin - 1;
for (int j = begin; j <= end - 1; ++j)
{
if (v[j] <= pivot) swap(v[j], v[++i]);
}
swap(v[i + 1], v[end]);
return i + 1;
}

i i(含)左边的元素都小于等于pivot
j 当前扫描到的元素
p begin
r end

i和j两个指针将[begin, end - 1]区间分成了三个部分(位置j待定)：

[begin, i] 元素都小于等于pivot
[i + 1, j) 元素都大于pivot
(j, end - 1) 待扫描

int partition(vector<int> &v, int begin, int end)
{
int pivot = v[end], i = begin;
for (int j = begin; j <= end - 1; ++j)
{
if (v[j] <= pivot) swap(v[j], v[i++]);
}
swap(v[i], v[end]);
return i;
}

## 双边扫描

int partition(vector<int> &v, int begin, int end)
{
int pivot = v[end], l = begin, r = end - 1;
while (l <= r)
{
while(v[l] < pivot && l <= r) ++l;
while(v[r] >= pivot && l <= r) --r;
if (l >= r) break;
swap(v[l], v[r]);
}
swap(v[l], v[end]);
return l;
}

## 随机选择pivot

int r = begin + rand() % (end - begin);
swap(v[r], v[end]);

# 完整代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int partition(vector<int> &v, int begin, int end)
{
// int r = begin + rand() % (end - begin);
// swap(v[r], v[end]);
int pivot = v[end], i = begin;
for (int j = begin; j <= end - 1; ++j)
{
if (v[j] <= pivot) swap(v[j], v[i++]);
}
swap(v[i], v[end]);
return i;
}

void qsort(vector<int> &v, int begin, int end)
{
if (begin >= end) return;
int p = partition(v, begin, end);
qsort(v, begin, p - 1);
qsort(v, p + 1, end);
}

void qsort(vector<int> &v)
{
qsort(v, 0, v.size() - 1);
}

void print(vector<int> &v)
{
for (int i = 0; i < v.size(); ++i)
{
cout<<v[i]<<" ";
}
cout<<endl;
}

bool check(vector<int> &v)
{
for (int i = 0; i < v.size() - 1; ++i)
{
if (v[i] > v[i + 1]) return false;
}
return true;
}

int main()
{
vector<int> v{1, 2, 2, 3, 3, 3, 4, 5};

int c = 0;
while(next_permutation(v.begin(), v.end()))
{
++c;
vector<int> a(v);
qsort(a);

if (check(a) == false)
{
cout<<"Wrong: "<<endl;
print(v);
cout<<"-->"<<endl;
print(a);
break;
}
}
cout<<"Tested "<<c<<" cases"<<endl;
}