练练手

练了七个小时...
爪巴
两种写法都可以

  • 先引入实现随机数的函数

    #include <random>
    #include <ctime>
    
    inline static int getRandomInt(int l,int r){
        static mt19937 mt(time(0));
        uniform_int_distribution<int> dist(l,r);
        return dist(mt);
    }
    
  • 第一种写法

    // 快速排序,指针版
    //
    // 把 [start, end) 中的所有元素按照 fun 返回
    // fun函数必须返回bool值
    //
    template <class T1, class T2> 
    void quickSort_v1(T1 *start, T1 *end, T2 fun) {
        
        //记得是大于等于,有些时候会出现start = end的情况
        //与mergesort有区别
        if (start >= end - 1) return;
    
        //随机化
        swap(*start, *(start+getRandomInt(0,end-start-1)) );
        T1 base = *start;
        T1 *lp = start, *rp = end - 1;
    
        while (lp < rp) {
            //右侧找到第一个小的
            while ( fun(*rp, base) && lp < rp) --rp;
            //插到最左边,别忘了++lp
            if (lp < rp) {
                swap(*lp,*rp);
                ++lp;
            }
            //左侧找到第一个大的
            while ( fun(*rp, base) && lp < rp) ++lp;
            //插到最右边,别忘了--rp
            if (lp < rp) {
                swap(*lp,*rp);
                --rp;
            }
        }
        
        //别忘了把标记放回去
        *lp = base;
    
        //求解左区间
        quickSort_v1(start, lp, fun);
        //求解右区间,记着把flag略过去
        quickSort_v1(lp + 1, end, fun);
    }
  • 第二种写法

    template<class T1, class T2>
    void quickSort_v2(T1* start, T1* end, T2 fun) {
        if(start >= end-1 )  return ;
        
        //随机
        swap(*(end-1), *(start+getRandomInt(0,end-start-1)) );
        T1 base = *(end-1);
        T1* pos = start;
    
        //把小于base的元素都放到左边,类似于冒泡排序
        for(T1* tmp = start; tmp!=end-1; ++tmp){
            if( fun(*tmp, base) ){
                 swap(*pos,*tmp);
                 pos++;
            }
        }
        
        //把标签放回去
        swap(*pos,*(end-1));
    
        quickSort_v2(start, pos, fun);
        quickSort_v2(pos+1, end, fun);
    }

至于说这为啥是O(NlogN)的,我真没有看懂。

啊对了,没事别自己写,浪费生命,而且算法谁考这么简单的东西呀。

乖乖用玄学优化好的sort()保命吧~

Last modification:April 6th, 2020 at 10:36 pm
Compared with money, your comment could inspire me more.
相较于钱财,你的留言更能激发我创作的灵感