排序算法的应用

用排序做集合运算 - 子集，交集，并集与差集

上一节我们讲了排序算法，包括快速排序sort,堆排序partial_sort和归并排序stable_sort。并且讲了排序的第一个用法，二分法差找。
二分法是针对一个排序后的容器的用法，如果是多个有序容器，我们就可以快速地在其基础上进行集合的求子集，交集，并集与差集等运算。

我们还是先看一下图，排序相关算法都有哪些内容：

sort2.png

子集std::includes

std::includes算法用于判断第一个迭代器是否包含第二个迭代器中的所有元素。

我们构造一个小的素数的集合，看看它是不是[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";
    }

唯一提醒一点，用std::includes算法之前，一定要确保两个容器都是同样有序的。

集合合并

集合合并就是简单将两个排序好的组结合并到一起。所以，被合并到的结构，一定要有足够的空间。
为了避免空间不足，我们可以使用list容器。
不过，我们都知道，std::list是一个链表，是不支持随机访问的迭代器的。这样，std::sort算法无法应用到list容器上。但是，面向对象语言的好处在此时又发挥出来了，list容器本身提供了一个更高效的sort函数。
后面我们会专题讲算法和容器的方法的关系，总体来说，算法是为了通用性，不考虑内部实现，为同类容器提供同一类算法。而容器自己的方法则提供针对这个容器的最优实现。
多说几句，这就是算法从面向对象的方法中脱离出来的好处。对象的方法，只在针对这个容器有较优化的实现时才会定义，比如vector的push_back很快，于是这个方法就存在。但是push_front不快，于是就没有这个方法。deque和list才有。针对于array,vector和deque，它们都支持随机访问的迭代器，所以可以将通用的sort, partial_sort和stable_sort算法应用到它们的结构上，所以它们不需要再提供这么多方法。
以后我们凡是发现某一具体容器提供了与算法同名或者功能相同的方法，应该优化使用容器定义的，因为没有特殊好处，是不会定义它的。要么是通用算法不管用，要么是通用算法效率低。如果容器没有定义，再从算法库中选一个最优的。

我们看例程：

    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

如果有重复元素，则重复元素就会让其重复，没有去重操作。

比如我们增加一个重复的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的基础上，去掉重复的元素。比如上例中的重复的3,就会被去除掉一个。

我们再看个例子：

    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 

有一点请大家特别注意，并集是排除了两个容器的公共元素的重复，如果一个容器本身的值是重复的，求并集可不管这个事情。

例：

    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;

因为union_numberj里存入了两个-1,做完set_union还是两个，这个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 

交集

两个容器中相同的部分：

    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;

不同于并集，交集的数目就少了，输出如下：

Intersection:1 2 3 100

差集和对称差集

差集有两种算法：一种是算第一容器中有的，减去两个容器中的交集，算法是set_difference。第二种是两个容器的并集，减出两个容器的差集，算法是set_symmetric_difference。
一般，第一种称为差集，第二种称为对称差。

名称	差集	对称差集
包含元素	第一容器 - 交集	并集 - 交集
算法	std::set_difference	std::set_symmetric_difference

我们还是看个例子就很容易理解了。

    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 

因为diff_number中的数字很少，减去并集，set_difference就剩一个-1了。但是对称差就是一个很大的集合了。

内部两个已排序空间合并

比如我们本来应该用std::merge算法来合并的，结果直接调用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);

这时的结果是这样的：

1 2 3 -3 -2 -1 

用排序当然是可以解决这个问题的。但是针对两个有序的子序间，我们有更好的办法：

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

std::inplace_merge就是在同一个容器内做merge，使其变得有序的算法。

经过上面一折腾，如果又变成有序的了：

-3 -2 -1 1 2 3 

如何判断一个容器或者区间是否有序？

我们之前学会了做子集，交集，并集，差集等各种操作。但是这样集合操作依赖于已经排序，我们怎样知道是不是已经排好序了呢？C++11又出来帮忙了，自C++11始，为我们提供了判断是否有序，是否分区等的算法。

从此以后，我们不需要上来就做排序了，可以先判断一下，没排好再排嘛：

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

同样的函数还有is_partitioned和is_heap。

另外，我们还可以知道，是到哪个元素开始，这个有序，或者划分或堆被破坏了。算法为is_sorted_until，is_partition_until和is_heap_until.

例：看看我们刚才inplace_merge之前，是哪个元素开始破坏了有序吧：

    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

因为当时，part1的值为

1 2 3 -3 -2 -1 

小结

好了，排序相关的主要算法就是这么多。

除了查找元素中的lower_bound,upper_bound,equal_range和heap算法中的push_heap和pop_heap，划分区间的partition_copy，其他主要算法我们都已经学完了。

本节我们学了两个排序之后的容器或者区间的集合的求子集，交，并，差，对称差操作。一个容器内两个区间的合并。
如果不确定是否已经排好序了，C++11为我们提供了一系列算法来进行判断。

好了，最后再更新一下大图，我们在算法地图上又进了一大步。
所有打绿勾的都是已经学过的了。

Paste_Image.png