快速排序

未做改进的快排

步骤:
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;
    }
};
全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务