数据结构
排序算法
快速排序
- 快速排序的做法是通过找到一个枢纽（pivot），这个枢纽可以将数组划分为两部分，一部分比枢纽大，另一部分比枢纽小。然后将这两部分依次递归处理，找到他们各自的枢纽。
- 该排序的思想是通过分治的思想，将问题规模变小， 依次逐步解决它们。
因此，在实现该算法上，可以划分为两部分：
- 第一部分是如何找到枢纽（pivot），函数名为_partition（主要与标准库的partition函数做区分）;
- 第二部分是将递归分治，函数名为quicksort；
第一部分
template <typename T, typename CmpFn>
T _partition(T low, T high, CmpFn cmp_fn) {
// 选定*hight为枢纽（pivot）
auto pivot = *high;
auto p = low-1;
for(auto it=low; it < high; ++it) {
// 判断是否需要交换，如果需要的话，则交换
if(cmp_fn(*it, pivot)) {
// 将p所指位置更新，交换*it，*p元素
++p;
swap(*it, *p);
}
}
// 将p所指位置更新，交换*it与*hight的元素
++p;
swap(*high, *p);
// 返回实际划分到的枢纽（pivot）的位置
return p;
}
第二部分
template <typename T, typename CmpFn>
void quicksort(T low, T high, CmpFn cmp_fn) {
// 判断需要继续递归分治下去
if(low < high) {
// 划分，得到枢纽的同时划分两部分，
// 使得一部分大于枢纽，另一部分小于枢纽
auto pivot = _partition(low, high, cmp_fn);
// 递归，分治下去
quicksort(low, pivot-1, cmp_fn);
quicksort(pivot+1, high, cmp_fn);
}
}
// 模版特化版本
template <typename T>
void quicksort(T low, T high) {
if(low < high) {
auto pivot = _partition(low, high, greater<T>());
quicksort(low, pivot-1);
quicksort(pivot+1, high);
}
}
下面进行AB测试，判断排序算法是否正确(完整代码)。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
using namespace std;
template <typename T, typename CmpFn>
T _partition(T low, T high, CmpFn cmp_fn) {
// 选定*hight为枢纽（pivot）
auto pivot = *high;
auto p = low-1;
for(auto it=low; it < high; ++it) {
// 判断是否需要交换，如果需要的话，则交换
if(cmp_fn(*it, pivot)) {
// 将p所指位置更新，交换*it，*p元素
++p;
swap(*it, *p);
}
}
// 将p所指位置更新，交换*it与*hight的元素
++p;
swap(*high, *p);
// 返回实际划分到的枢纽（pivot）的位置
return p;
}
template <typename T, typename CmpFn>
void quicksort(T low, T high, CmpFn cmp_fn) {
if(low < high) {
auto pivot = _partition(low, high, cmp_fn);
quicksort(low, pivot-1, cmp_fn);
quicksort(pivot+1, high, cmp_fn);
}
}
template <typename T>
void quicksort(T low, T high) {
if(low < high) {
auto pivot = _partition(low, high, greater<T>());
quicksort(low, pivot-1);
quicksort(pivot+1, high);
}
}
int main() {
auto ABTest_fn = [](const size_t size, default_random_engine& e) -> bool {
vector<int> m1(size);
for(auto& c : m1) {
c = e();
}
vector<int> m2 = m1;
sort(begin(m1), end(m1), less<int>());
quicksort(begin(m2), end(m2)-1, less<int>());
auto cmp_fn = [](const vector<int>& m1, const vector<int>& m2) -> bool {
bool flag = (m1.size() == m2.size());
if(flag) {
for(size_t i=0; i < m1.size(); ++i) {
if(m1[i] != m2[i]) {
flag = false;
break;
}
}
}
return flag;
};
return cmp_fn(m1, m2);
};
bool flag = true;
default_random_engine e;
const size_t loop_num = 10000;
const size_t size = 1000;
for(size_t i=0; i < loop_num && flag; ++i) {
flag = ABTest_fn(size, e);
}
cout << "Did AB test pass ? (1:0):" << endl << flag << endl;
return 0;
}
