代码

#include<iostream>

#include<vector>

using namespace std;

class Solution

{

public:

    //快速排序接口

    void quickSort(vector<int> &vec, vector<int>::iterator begin, vector<int>::iterator end)

    {

        if (end != vec.begin() && begin < end - 1)

        {

            vector<int>::difference_type pivot = partition(vec, begin, end - 1);

            quickSort(vec, begin, vec.begin() + pivot);

            quickSort(vec, vec.begin() + pivot + 1, end);

        }

    }

private:

    //实现移动

    vector<int>::difference_type partition(vector<int> &vec, vector<int>::iterator begin, vector<int>::iterator end)

    {

        findMidOfThree(vec,begin,end);

        while (begin < end)

        {

            while (begin < end && *begin < *end) end--;

            swap(*begin, *(end));

            while (begin < end && *begin < *(end)) begin++;

            swap(*begin, *(end));

        }

        return begin-vec.begin();

    }

    //实现查找中位数并且交换位置，防止达到最坏复杂度

    void findMidOfThree(vector<int> &vec, vector<int>::iterator begin, vector<int>::iterator end)

    {

        vector<int>::iterator midIter = (begin + (end-begin)/2);

        if ((*begin > *end&&*begin < *midIter) ||

            (*begin<*end&&*begin>*midIter))

            return;

        if ((*midIter > *begin&&*midIter < *end) ||

            (*midIter > *end&&*midIter < *begin))

            swap(*midIter, *begin);

        if ((*end > *begin&&*end < *midIter) ||

            (*end > *midIter&&*end < *begin))

            swap(*end, *begin);

    }

};

#include"快速排序.h"

void main()

{

    Solution s;

    vector<int> test = { 1,3,5,7,9,2,4,6,8,10 };

    s.quickSort(test, test.begin(), test.end());

    for (auto i : test)

    {

        cout << i << " ";

    }

    cout << endl;

}

总结

最难的一点就是要控制左闭右开的区间，一些边界条件非常难控制。

巴特西

快速排序——C++左闭右开区间实现

代码

总结

最新文章

热门文章