本文首發(fā)于個(gè)人CSDN博客: https://blog.csdn.net/ggq89/article/details/88817085

假設(shè)有一個(gè)容器鸽捻，保存了 100 萬(wàn)個(gè)數(shù)值特咆，但我們只對(duì)其中最小的 100 個(gè)元素的順序感興趣』瑁可以對(duì)容器的全部?jī)?nèi)容排序掘剪，然后選擇前 100 個(gè)元素，但這樣處理會(huì)使效率低奈虾。這時(shí)候需要使用部分排序 partial_sort夺谁，高效的獲得這些數(shù)中的前100個(gè)最小數(shù)的順序。

1. partial_sort 接口說(shuō)明……

partial_sort有兩個(gè)版本肉微，一個(gè)默認(rèn)以小于（less-than操作符）作為比較規(guī)則匾鸥，出來(lái)的順序?yàn)檫f增排列。另一個(gè)可以傳入一個(gè)比較函數(shù)碉纳，即調(diào)用者指定一個(gè)比較規(guī)則勿负。

partial_sort(beg,mid,end)
partial_sort(beg,mid,end,comp)

對(duì)容器中的(mid-beg)個(gè)元素進(jìn)行排序，partial_sort 完成之后村象，從beg到mid(但不包括mid)范圍內(nèi)的元素時(shí)有序的笆环，且大于（或者指定的comp函數(shù)）mid之后的元素。未排序元素之間的次序是不確定的厚者，即partial_port不是穩(wěn)定排序算法躁劣。

2. partial_sort 用法舉例

下面這段代碼演示了 partial_sort() 算法的工作方式：

size_t count {5}; // Number of elements to be sorted
std::vector<int> numbers {22, 7, 93, 45, 19, 56, 88, 12, 8, 7, 15, 10};
std::partial_sort(std::begin(numbers), std::begin(numbers) + count, std::end(numbers));

執(zhí)行partial__sort()后的效果如下圖所示：

partial_sort() 算法的操作

需要注意的是，不能保持未排序元素的原始順序库菲。在執(zhí)行 partial_sort() 后后面元素的順序是不確定的账忘，這取決于具體的實(shí)現(xiàn)。

也可以指定不同的比較函數(shù)熙宇。例如：

std::partial_sort(std::begin(numbers), std::begin(numbers) + count, std:: end (numbers) , std::greater<>());

現(xiàn)在鳖擒，number 中最大的 count 個(gè)元素會(huì)是容器開(kāi)始處的一個(gè)降序序列。以上語(yǔ)句的輸出結(jié)果為：

93 88 56 45 22 7 19 12 8 7 15 10

同樣的烫止，不能保持 numbers 中未排序元素的原始順序蒋荚。

3. partial_sort 原理概述

那么 partial_sort 的原理是什么呢？是堆排序馆蠕！

partial_sort的原理：

1. 對(duì)原始容器內(nèi)區(qū)間為[first, middle)的元素執(zhí)行 make_heap() 操作構(gòu)造一個(gè)大頂堆期升，
2. 然后遍歷剩余區(qū)間[middle, last)中的元素惊奇，剩余區(qū)間的每個(gè)元素均與大頂堆的堆頂元素進(jìn)行比較（大頂堆的堆頂元素為最大元素，該元素為第一個(gè)元素播赁，很容易獲得）颂郎，若堆頂元素較小，則交換堆頂元素和遍歷得到的元素值（pop_heap ）容为，并重新調(diào)整該大頂堆以維持該堆為大頂堆（adjust_heap）乓序。
3. 遍歷結(jié)束后，[first, middle)區(qū)間內(nèi)的元素便是排名在前的m個(gè)元素坎背，再對(duì)該堆做一次堆排序 sort_heap() 便可得到最后的結(jié)果替劈。

下圖為partial_sort 算法的步驟詳解：

partial_sort() 算法步驟詳解

4. partial_sort 源碼講解

下面是STL中 partial_sort 的源碼講解，考慮到篇幅沼瘫，這里只列出第一個(gè)版本的抬纸。

// 版本一
template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
    RandomAccessIterator middle,
    RandomAccessIterator last) {
        __partial_sort(first, middle, last, value_type(first));
}
 
template <class RandomAccessIterator, class T>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
    RandomAccessIterator last, T*) {
        make_heap(first, middle); //將區(qū)間[first, middle)構(gòu)造為一個(gè)堆結(jié)構(gòu)
        for (RandomAccessIterator i = middle; i < last; ++i)
            if (*i < *first)    // 遍歷堆以外的元素，并將更優(yōu)的元素放入堆中
                __pop_heap(first, middle, i, T(*i), distance_type(first)); // first值放i中耿戚，i的原值融入heap并調(diào)整
        sort_heap(first, middle); // 對(duì)最終的堆進(jìn)行排序
}

先來(lái)分析 make_heap 算法湿故， 該算法將一段指定的數(shù)據(jù)排列出max-heap：

template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __make_heap(first, last, value_type(first), distance_type(first));
}
 
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
    Distance*) {
        if (last - first < 2) return; // 如果長(zhǎng)度為0或1，不必重新排列    
        Distance len = last - first;
        // 找出第一個(gè)需要重新排列的子樹(shù)頭部（即最后一個(gè)子樹(shù)）膜蛔，以parent標(biāo)記坛猪。由于任何葉子節(jié)點(diǎn)都不需要處理。
        // parent 命名不佳皂股， 為 holeIndex 更好
        Distance parent = (len - 2)/2; 
 
        while (true) {
            // 重排以parent為首的子樹(shù)墅茉，以len為操作范圍
            __adjust_heap(first, parent, len, T(*(first + parent)));
            if (parent == 0) return; // 走完根節(jié)點(diǎn)，結(jié)束
            parent--; // 向前排列前一個(gè)節(jié)點(diǎn)
        }
}

下面來(lái)重點(diǎn)分析 __adjust_heap 算法呜呐， 該算法調(diào)整從first開(kāi)始的len個(gè)元素就斤，洞號(hào)為holeIndex，洞值為value蘑辑， 最終獲得一個(gè) max-heap 洋机。

template <class RandomAccessIterator, class Distance, class T>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
    Distance len, T value) {
        Distance topIndex = holeIndex;
        Distance secondChild = 2 * holeIndex + 2; // holeIndex的右子節(jié)點(diǎn)
        while (secondChild < len) {
            // 比較holeIndex兩個(gè)子節(jié)點(diǎn)的值，用secondChild代表值較大的子節(jié)點(diǎn)
            if (*(first + secondChild) < *(first + (secondChild - 1)))
                secondChild--;   
            // 令較大子值為洞值洋魂，注意：原洞值已在函數(shù)形參value中得以保存
            *(first + holeIndex) = *(first + secondChild); 
            // 再讓洞號(hào)下移到左子節(jié)點(diǎn)處灾票，
            holeIndex = secondChild;
            // 算出新的洞節(jié)點(diǎn)的右子節(jié)點(diǎn)
            secondChild = 2 * (secondChild + 1);
        }
        // 如果沒(méi)有右子節(jié)點(diǎn)收夸，只有左子節(jié)點(diǎn)
        if (secondChild == len) { 
            // 令左子節(jié)點(diǎn)為洞值，然后將洞號(hào)下移到左子節(jié)點(diǎn)
            *(first + holeIndex) = *(first + (secondChild - 1));
            holeIndex = secondChild - 1;
        }
        // 將原洞值push到新的洞號(hào)中儿惫。
        // 以下語(yǔ)句的效果類(lèi)似于： *(first + holeIndex) = value; 
        __push_heap(first, holeIndex, topIndex, value);
}

進(jìn)一步講解__adjust_heap 算法 調(diào)用的 __push_heap 算法斯棒，該算實(shí)現(xiàn)將新元素value push到max-heap中topIndex到holeIndex的合適位置中府框，其中max-heap的起始位置是first蝴猪。

template <class RandomAccessIterator, class Distance, class T>
void __push_heap(RandomAccessIterator first, Distance holeIndex,
    Distance topIndex, T value) {
        Distance parent = (holeIndex - 1) / 2;  // 找到父節(jié)點(diǎn)
        // 當(dāng)尚未達(dá)到頂端投蝉， 且父節(jié)點(diǎn)的值小于新值（不符合max-heap的次序特性）
        while (holeIndex > topIndex && *(first + parent) < value) {
            *(first + holeIndex) = *(first + parent); // 移動(dòng)父值到洞號(hào)處
            holeIndex = parent; // 調(diào)整洞號(hào)為父節(jié)點(diǎn)
            parent = (holeIndex - 1) / 2; // 新洞的父節(jié)點(diǎn)
        }  // 循環(huán)到頂端，或者滿(mǎn)足max-heap的順序?yàn)橹?        *(first + holeIndex) = value; // 將新值放入循環(huán)完得到的洞號(hào)心剥，完成push操作
}

再回頭看 __partial_sort 算法启搂，當(dāng)*i < *first時(shí)硼控，代碼中沒(méi)有互換i所指元素和first所指元素。實(shí)際上這一步操作是在 __pop_heap 函數(shù) 完成的胳赌，在該函數(shù)內(nèi)，先將要first元素放入指定的result匙隔，然后用新值value去調(diào)整max-heap疑苫。

template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                       RandomAccessIterator result, T value, Distance*) {
  *result = *first; // 將heap頂端元素值放入 result中
  // 重新調(diào)整heap，洞號(hào)為0纷责，欲調(diào)整的新值為value
  __adjust_heap(first, Distance(0), Distance(last - first), value);
}

最后來(lái)看看 sort_heap 算法捍掺，該算法將[first, last)中的元素由堆序變?yōu)樵鲂蚺帕小Ｃ看螐棾龆训淖畲笾挡⒎湃胛膊吭偕牛缓罂s小堆的范圍挺勿，循環(huán)執(zhí)行彈出操作直至堆只剩下最后一個(gè)元素。

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
    while (last - first > 1)  // 直到只剩一個(gè)元素為止
        pop_heap(first, last--); // 每執(zhí)行一次喂柒，范圍縮小一格
}

template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __pop_heap_aux(first, last, value_type(first));
}
 
template <class RandomAccessIterator, class T>
inline void __pop_heap_aux(RandomAccessIterator first,
    RandomAccessIterator last, T*) {
        // 將first元素值（即最大值）放入last-1不瓶，然后重調(diào)[first, last-1)為max-heap
        __pop_heap(first, last-1, last-1, T(*(last-1)), distance_type(first));
}

參考文章：

• 《STL源碼剖析》 6.7.8 partial_sort, P386.
• STL之partial_sort排序?qū)W習(xí)： https://blog.csdn.net/jfkidear/article/details/8922974
• C++ partial_sort(STL partial_sort)排序算法詳解： http://c.biancheng.net/view/564.html
• 無(wú)聊寫(xiě)排序之 ----部分排序(Partial Sort)： https://blog.csdn.net/dreamhougf/article/details/47106849
• 【STL】算法 — partial_sort： https://blog.csdn.net/nestler/article/details/25882261