排序算法的應(yīng)用

用排序做集合運(yùn)算 - 子集，交集，并集與差集

上一節(jié)我們講了排序算法，包括快速排序sort,堆排序partial_sort和歸并排序stable_sort。并且講了排序的第一個(gè)用法，二分法差找。
二分法是針對(duì)一個(gè)排序后的容器的用法，如果是多個(gè)有序容器，我們就可以快速地在其基礎(chǔ)上進(jìn)行集合的求子集，交集，并集與差集等運(yùn)算。

我們還是先看一下圖，排序相關(guān)算法都有哪些內(nèi)容：

sort2.png

子集std::includes

std::includes算法用于判斷第一個(gè)迭代器是否包含第二個(gè)迭代器中的所有元素。

我們構(gòu)造一個(gè)小的素?cái)?shù)的集合，看看它是不是[1,100]的子集：

    std::vector<int> prime_numbers;
    prime_numbers.push_back(2);
    prime_numbers.push_back(3);
    prime_numbers.push_back(5);
    prime_numbers.push_back(7);
    prime_numbers.push_back(11);
    prime_numbers.push_back(13);
    
    std::sort(odd_even.begin(),odd_even.end());
    std::sort(prime_numbers.begin(),prime_numbers.end());
    
    if(std::includes(odd_even.cbegin(), odd_even.cend(), prime_numbers.cbegin(), prime_numbers.cend())){
        std::cout<<"odd_even includes prime_numbers";
    }else{
        std::cout<<"odd_even does not include prime_numbers";
    }

唯一提醒一點(diǎn)，用std::includes算法之前，一定要確保兩個(gè)容器都是同樣有序的。

集合合并

集合合并就是簡(jiǎn)單將兩個(gè)排序好的組結(jié)合并到一起。所以，被合并到的結(jié)構(gòu)，一定要有足夠的空間。
為了避免空間不足，我們可以使用list容器。
不過，我們都知道，std::list是一個(gè)鏈表，是不支持隨機(jī)訪問的迭代器的。這樣，std::sort算法無(wú)法應(yīng)用到list容器上。但是，面向?qū)ο笳Z(yǔ)言的好處在此時(shí)又發(fā)揮出來了，list容器本身提供了一個(gè)更高效的sort函數(shù)。
后面我們會(huì)專題講算法和容器的方法的關(guān)系，總體來說，算法是為了通用性，不考慮內(nèi)部實(shí)現(xiàn)，為同類容器提供同一類算法。而容器自己的方法則提供針對(duì)這個(gè)容器的最優(yōu)實(shí)現(xiàn)。
多說幾句，這就是算法從面向?qū)ο蟮姆椒ㄖ忻撾x出來的好處。對(duì)象的方法，只在針對(duì)這個(gè)容器有較優(yōu)化的實(shí)現(xiàn)時(shí)才會(huì)定義，比如vector的push_back很快，于是這個(gè)方法就存在。但是push_front不快，于是就沒有這個(gè)方法。deque和list才有。針對(duì)于array,vector和deque，它們都支持隨機(jī)訪問的迭代器，所以可以將通用的sort, partial_sort和stable_sort算法應(yīng)用到它們的結(jié)構(gòu)上，所以它們不需要再提供這么多方法。
以后我們凡是發(fā)現(xiàn)某一具體容器提供了與算法同名或者功能相同的方法，應(yīng)該優(yōu)化使用容器定義的，因?yàn)闆]有特殊好處，是不會(huì)定義它的。要么是通用算法不管用，要么是通用算法效率低。如果容器沒有定義，再?gòu)乃惴◣?kù)中選一個(gè)最優(yōu)的。

我們看例程：

    std::list<int> minus_number;
    minus_number.push_back(-1);
    minus_number.push_back(-5);
    minus_number.sort();
    
    std::sort(odd_even.begin(),odd_even.end());
    
    std::cout<<"Merged:";
    std::merge(minus_number.begin(), minus_number.end(), odd_even.begin(), odd_even.end(),
               std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

輸出如下：

Merged:-5 -1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

如果有重復(fù)元素，則重復(fù)元素就會(huì)讓其重復(fù)，沒有去重操作。

比如我們?cè)黾右粋€(gè)重復(fù)的3：

    std::list<int> minus_number;
    minus_number.push_back(-1);
    minus_number.push_back(-5);
    minus_number.push_front(3);
    minus_number.sort();
    
    std::sort(odd_even.begin(),odd_even.end());
    
    std::cout<<"Merged:";
    std::merge(minus_number.begin(), minus_number.end(), odd_even.begin(), odd_even.end(),
               std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

輸出如下：

Merged:-5 -1 1 2 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

并集

并集就是在merge的基礎(chǔ)上，去掉重復(fù)的元素。比如上例中的重復(fù)的3,就會(huì)被去除掉一個(gè)。

我們?cè)倏磦€(gè)例子：

    std::list<int> union_number;
    union_number.push_front(1);
    union_number.push_back(2);
    union_number.push_front(3);
    union_number.push_back(100);
    union_number.push_front(-1);
    union_number.sort();
    
    std::sort(odd_even.begin(),odd_even.end());
    
    std::cout<<"Union:";
    std::set_union(union_number.begin(), union_number.end(), odd_even.begin(), odd_even.end(),
               std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

輸出如下：

Union:-1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

有一點(diǎn)請(qǐng)大家特別注意，并集是排除了兩個(gè)容器的公共元素的重復(fù)，如果一個(gè)容器本身的值是重復(fù)的，求并集可不管這個(gè)事情。

例：

    std::list<int> union_number;
    union_number.push_front(1);
    union_number.push_back(2);
    union_number.push_front(3);
    union_number.push_back(100);
    union_number.push_front(-1);
    union_number.push_back(-1);
    union_number.sort();
    
    std::sort(odd_even.begin(),odd_even.end());
    
    std::cout<<"Union:";
    std::set_union(union_number.begin(), union_number.end(), odd_even.begin(), odd_even.end(),
               std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

因?yàn)閡nion_numberj里存入了兩個(gè)-1,做完set_union還是兩個(gè)，這個(gè)set_union算法不管的啊。
輸出如下：

Union:-1 -1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

交集

兩個(gè)容器中相同的部分：

    std::list<int> intersection_number;
    intersection_number.push_front(1);
    intersection_number.push_back(2);
    intersection_number.push_front(3);
    intersection_number.push_back(100);
    intersection_number.push_front(-1);
    intersection_number.sort();
    
    std::sort(odd_even.begin(),odd_even.end());
    
    std::cout<<"Intersection:";
    std::set_intersection(intersection_number.begin(), intersection_number.end(), odd_even.begin(), odd_even.end(),
                   std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

不同于并集，交集的數(shù)目就少了，輸出如下：

Intersection:1 2 3 100

差集和對(duì)稱差集

差集有兩種算法：一種是算第一容器中有的，減去兩個(gè)容器中的交集，算法是set_difference。第二種是兩個(gè)容器的并集，減出兩個(gè)容器的差集，算法是set_symmetric_difference。
一般，第一種稱為差集，第二種稱為對(duì)稱差。

我們還是看個(gè)例子就很容易理解了。

    std::list<int> diff_number;
    diff_number.push_front(1);
    diff_number.push_back(2);
    diff_number.push_front(3);
    diff_number.push_back(100);
    diff_number.push_front(-1);
    diff_number.sort();
    
    std::sort(odd_even.begin(),odd_even.end());
    
    std::cout<<"Difference:";
    std::set_difference(diff_number.begin(), diff_number.end(), odd_even.begin(), odd_even.end(),
                          std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;
    
    std::list<int> diff_number2;
    diff_number2.push_front(1);
    diff_number2.push_back(2);
    diff_number2.push_front(3);
    diff_number2.push_back(100);
    diff_number2.push_front(-1);
    diff_number2.sort();
    
    std::sort(odd_even.begin(),odd_even.end());
    
    std::cout<<"Difference2:";
    std::set_symmetric_difference(diff_number2.begin(), diff_number2.end(), odd_even.begin(), odd_even.end(),
                        std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

Difference:-1 
Difference2:-1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 

因?yàn)閐iff_number中的數(shù)字很少，減去并集，set_difference就剩一個(gè)-1了。但是對(duì)稱差就是一個(gè)很大的集合了。

內(nèi)部?jī)蓚€(gè)已排序空間合并

比如我們本來應(yīng)該用std::merge算法來合并的，結(jié)果直接調(diào)用splice去連接了。

    std::list<int> part1;
    part1.push_back(1);
    part1.push_front(2);
    part1.push_back(3);
    part1.sort();
    
    std::list<int> part2;
    part2.push_back(-1);
    part2.push_back(-2);
    part2.push_back(-3);
    part2.sort();
    
    part1.splice(part1.end(), part2);

這時(shí)的結(jié)果是這樣的：

1 2 3 -3 -2 -1 

用排序當(dāng)然是可以解決這個(gè)問題的。但是針對(duì)兩個(gè)有序的子序間，我們有更好的辦法：

    auto pos3 = std::find(part1.begin(), part1.end(), 3);
    std::inplace_merge(part1.begin(), ++pos3,part1.end());

std::inplace_merge就是在同一個(gè)容器內(nèi)做merge，使其變得有序的算法。

經(jīng)過上面一折騰，如果又變成有序的了：

-3 -2 -1 1 2 3 

如何判斷一個(gè)容器或者區(qū)間是否有序？

我們之前學(xué)會(huì)了做子集，交集，并集，差集等各種操作。但是這樣集合操作依賴于已經(jīng)排序，我們?cè)鯓又朗遣皇且呀?jīng)排好序了呢？C++11又出來幫忙了，自C++11始，為我們提供了判斷是否有序，是否分區(qū)等的算法。

從此以后，我們不需要上來就做排序了，可以先判斷一下，沒排好再排嘛：

    if(!std::is_sorted(odd_even.cbegin(), odd_even.cend())){
        std::sort(odd_even.begin(),odd_even.end());
    }

同樣的函數(shù)還有is_partitioned和is_heap。

另外，我們還可以知道，是到哪個(gè)元素開始，這個(gè)有序，或者劃分或堆被破壞了。算法為is_sorted_until，is_partition_until和is_heap_until.

例：看看我們剛才inplace_merge之前，是哪個(gè)元素開始破壞了有序吧：

    std::list<int> part1;
    part1.push_back(1);
    part1.push_front(2);
    part1.push_back(3);
    part1.sort();
    
    std::list<int> part2;
    part2.push_back(-1);
    part2.push_back(-2);
    part2.push_back(-3);
    part2.sort();
    
    part1.splice(part1.end(), part2);
    
    std::cout<<"First disordered item:"<<*std::is_sorted_until(part1.cbegin(), part1.cend())<<"\n";

輸出為：

First disordered item:-3

因?yàn)楫?dāng)時(shí)，part1的值為

1 2 3 -3 -2 -1 

小結(jié)

好了，排序相關(guān)的主要算法就是這么多。

除了查找元素中的lower_bound,upper_bound,equal_range和heap算法中的push_heap和pop_heap，劃分區(qū)間的partition_copy，其他主要算法我們都已經(jīng)學(xué)完了。

本節(jié)我們學(xué)了兩個(gè)排序之后的容器或者區(qū)間的集合的求子集，交，并，差，對(duì)稱差操作。一個(gè)容器內(nèi)兩個(gè)區(qū)間的合并。
如果不確定是否已經(jīng)排好序了，C++11為我們提供了一系列算法來進(jìn)行判斷。

好了，最后再更新一下大圖，我們?cè)谒惴ǖ貓D上又進(jìn)了一大步。
所有打綠勾的都是已經(jīng)學(xué)過的了。

Paste_Image.png