算法分析：快速选择

使用类似快速排序的方法，找出第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,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,a.size() ⑴,k);
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!