算法分析:快速选择

使用类似快速排序的方法,找出第k小的元素。

k从0开始的。

使用了快速排序的部份函数 快速排序

    //快速选择
    template<typename Comparable>
    Comparable& quickSelect(vector<Comparable>& a, int left, int right, int k)
    {
        if (left + 10 <= right)//这个子数组大于10,继续使用快速排序
        {
            Comparable pivot = median3(a, left, right);//关键值
            int i = left;//i指向左侧
            int j = right - 1;//j指向右侧,现在i和j都是已比较过的了,等下是先++和--
            while (true)
            {
                while (a[++i] < pivot) {}//小于关键值的元素是1直放在左侧,找出1个大的元素
                while (pivot < a[--j]) {}//大于关键值的元素是1直放在右侧,找出1个小的元素
                if (i < j)
                {
                    swap(a[i], a[j]);//i和j还没有交汇,交换位置
                }
                else
                {
                    break;//这个时候i指向的数是应当比关键值大的了
                }
            }
            swap(a[i], a[right - 1]);//将关键值放在i的位置
            if (k <= i)
            {
                return quickSelect(a, left, i - 1, k);//k在左侧的子序列中
            }
            else if(k > i + 1)
            {
                return quickSelect(a, i + 1, right, k);//k在右侧的子序列中
            }
            else
            {
                return a[i];
            }
           
        }
        else
        {
            //使用插入排序,数组大小小于10的时候
            insertionSort(a.begin() + left, a.begin() + right + 1);
            return a[k];//由于排序是在全部数组里面的,所以第k位置就是所要的值
        }
    }
    
    template<typename Comparable>
    Comparable& quickSelect(vector<Comparable>& a, int k)
    {
        return quickSelect(a, 0, a.size() ⑴, k);
    }

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 算法分析:快速选择

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡