算法分析：快速选择

使用类似快速排序的方法，找出第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);
    }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠