数据结构

排序算法

快速排序

快速排序的做法是通过找到一个枢纽（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;
}