快速排序

未做改进的快排

步骤：
1.把数组的最后一个元素作为划分值
2.使用荷兰国旗的partition算法划分为三部分（这个时候只有最后一个元素归位了）
3.然后对左侧范围和右侧范围采用递归进行划分
分析：划分值越靠近两端，复杂度越高，划分值越靠近中间，复杂度越低
最差的时间复杂度为O（N2）
注意一下：这里partition的时候，>区的初始位置要设置为最后一个元素，这个元素先不动，在划分结束后再把最后一个元素和大于区的第一个元素交换！！！如果把最后一个元素的后一个当做>区的初始位置的话会报错！！！因为我这里的递归是用的大于区的左边界，如果大于区没有元素的话，那这个边界就是无效元素了，没办法再进行下面的partition了！！！
其他partition过程和之前荷兰国旗问题相同

class QuickSort
{
public:
    void quicksort(vector<int>& v)
    {
        if (v.size() < 2)
            return;
        int l = 0;
        int r = v.size() - 1;
        myQuickSort(v, l, r);
    }
    void myQuickSort(vector<int>& v, int l, int r)
    {
        if (l < r)
        {
            vector<int> help = partition(v, l, r);
            myQuickSort(v, l, help[0]);      //<区做partition
            myQuickSort(v, r, help[1]);      //>区做partition
        }
        return;
    }
    vector<int> partition(vector<int>& v, int l, int r)
    {
        int s = l - 1;           //<区域
        int b = r ;           //>区域
        int i = l;               //当前值
        int target = v[r];
        while (i < b)
        {
            if (v[i] < target)
            {
                mySwap(v[i], v[s + 1]);
                i++;
                s++;
            }
            else if (v[i] > target)
            {
                mySwap(v[i], v[b - 1]);
                b--;
            }
            else
                i++;
        }
        mySwap(v[b],v[r]);
        vector<int> help;
        help.push_back(s);
        help.push_back(b);//把当前小于区和大于区的边界返回，以便下面分别对小于和大于区再次进行partition操作
        return help;
    }
    void mySwap(int& a, int& b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
};

随机快排（改进的快排）

在数组范围里，等概率随机选一个数作为划分值，把它放到最后去（其他的和上面一样）

class QuickSort2
{
public:
    void quicksort(vector<int>& v)
    {
        if (v.size() < 2)
            return;
        int l = 0;
        int r = v.size() - 1;
        myQuickSort(v, l, r);
    }
    void myQuickSort(vector<int>& v, int l, int r)
    {
        if (l < r)
        {
            srand((unsigned int) time (NULL));
            int random = l + rand() % (r - l + 1);//在l和r中随机挑一个位置作为划分值，与最后一个元素进行交换
            mySwap(v[r], v[random]);
            vector<int> help = partition(v, l, r);
            myQuickSort(v, l, help[0]);      //<区做partition
            myQuickSort(v, r, help[1]);      //>区做partition
        }
        return;
    }
    vector<int> partition(vector<int>& v, int l, int r)
    {
        int s = l - 1;           //<区域
        int b = r;           //>区域
        int i = l;               //当前值
        int target = v[r];
        while (i < b)
        {
            if (v[i] < target)
            {
                mySwap(v[i], v[s + 1]);
                i++;
                s++;
            }
            else if (v[i] > target)
            {
                mySwap(v[i], v[b - 1]);
                b--;
            }
            else
                i++;
        }
        mySwap(v[b], v[r]);
        vector<int> help;
        help.push_back(s);
        help.push_back(b);//把当前小于区和大于区的边界返回，以便下面分别对小于和大于区再次进行partition操作
        return help;
    }
    void mySwap(int& a, int& b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
};