數(shù)據(jù)結(jié)構(gòu)

排序算法

快速排序

1. 快速排序的做法是通過(guò)找到一個(gè)樞紐（pivot），這個(gè)樞紐可以將數(shù)組劃分為兩部分，一部分比樞紐大，另一部分比樞紐小。然后將這兩部分依次遞歸處理，找到他們各自的樞紐。
2. 該排序的思想是通過(guò)分治的思想，將問(wèn)題規(guī)模變小， 依次逐步解決它們。

因此，在實(shí)現(xiàn)該算法上，可以劃分為兩部分：

1. 第一部分是如何找到樞紐（pivot），函數(shù)名為_(kāi)partition（主要與標(biāo)準(zhǔn)庫(kù)的partition函數(shù)做區(qū)分）;
2. 第二部分是將遞歸分治，函數(shù)名為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);
    
    // 返回實(shí)際劃分到的樞紐（pivot）的位置
    return p;
}

第二部分

template <typename T, typename CmpFn>
void quicksort(T low, T high, CmpFn cmp_fn) {
    // 判斷需要繼續(xù)遞歸分治下去
    if(low < high) {
        // 劃分，得到樞紐的同時(shí)劃分兩部分，
        // 使得一部分大于樞紐，另一部分小于樞紐
        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);
    }
}

下面進(jìn)行AB測(cè)試，判斷排序算法是否正確(完整代碼)。

#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);
    
    // 返回實(shí)際劃分到的樞紐（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;
}