# 排序算法的应用

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

### 子集std::includes

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

    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::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

    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

### 并集

    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:-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

### 差集和对称差集

    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 

## 内部两个已排序空间合并

    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 

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

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

    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

1 2 3 -3 -2 -1 

+ 订阅