算法分析：快速選擇

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

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈