STL算法之排序算法

STL排序算法通常复杂度坏于线性，且必须要random-access Iterators。

所以，forward_list, list, associative and unordered contains 不提供随机访问迭代器，这些容器不能用排序算法。

但是，forward_list，list提供了成员函数sort，associative contains 自动排序，unordered contains不能排序。

通常，排序元素一次要比保持元素有序要更快。STL提供了不同的排序算法，根据需求选择适合的。

1.排序所有元素

1.1.普通排为有序

void

sort(RandomAccessIter beg, RandomAccessIter end);

使用operator < 排列元素为有序。历史上使用quicksort，但是since C++11使用introsort。

introsort正常使用quicksort，但是当复杂度要到平方时转换为heapsort。因此，

算法保证了复杂度nlogn，以前是“平均”复杂度nlogn。

//更改排序准则：

void

sort(RandomAccessIter beg, RandomAccessIter end, BinaryPredicate op);

使用op(elem1, elem2);二元谓词作为排序准则。

注意op必须是严格弱排序，在函数调用期间op不能改变状态。

1.2.保持相等元素的相对顺序的排序

void

stable_sort(RandomAccessIter beg, RandomAccessIter end, [BinaryPredicate op]);

相对于sort, 可以保持相等元素的相对顺序不变。

基于mergesort, 若有足够的外部内存：复杂度nlogn,否则，n*logn*logn的复杂度。

示例：

2.分割排序：保持一部分元素是有序的

void

partial_sort(RandomAccessIter beg, RandomAccessIter sortEnd,

                RandomAccessIter end, [BinaryPredicate op]);

特点：不排序所有元素，只排序[beg, sortEnd)，当这个区间有序后就停止排序。

若sortEnd == end, partial_sort()排序所有元素，平均情况下比sort()有更差性能，通常排序时间两倍于sort()。但是在最坏情况下有着更好性能。

通常使用heapsort，在任何情况下都保证了nlogn复杂度。

//排序同时复制版本：

3.根据某个位置排序：分割成两部分

void

nth_element(RandomAccessIter beg, RandomAccessIter nth, RandomAccessIter end, [BinaryPredicate op]);

将区间分割成：<=nth元素和>=nth元素两部分。或者根据op(elem1, elem2)分割。

第一个区间中元素<=第二个区间中任一元素。

适用于找出n highest或者lowest 元素。

线性复杂度。

由于你不知道排序后两个区间的确切排序准则，两个部分可能和nth有同样值。

4.根据确切的排序准则排序：不属于排序算法，属于Mutating Algorithm，所以不需要Random-access Iterator

(1) 移动元素到前端

ForwardIter

partion(ForwardIter beg, ForwardIter end, UnaryPredicate op);

BidirectionalIter

stable_partion(BidirectionalIter beg, BidirectionalIter end, UnaryPredicate op);

移动所有满足op(elem) == true的元素到区间前面。

stable_partion()维持匹配准则和不匹配准则的元素之间的相对顺序。

还需要分割复制元素时：用partion_copy()复制匹配准则的元素到到一个目的区间，不匹配准则的元素到另一个区间。

复杂度：

        partion(): 线性。

        stable_partion()：有足够内存，线性（numElems交换和call op()）；否则，nlogn(numElems次call op()，numElems * log(numElems)交换)。

调用之后，不知道第一个和第二个期间的元素数量。

(2) 分割成两个子区间

pari<OutPutIter1, OutputIter2>

partion_copy(InputIter sourceBeg, InputIter sourceEnd

            OutputIter1 destTureBeg, OutputIter2 destFalseBeg,

             UnaryPredicate op);

根据op()分成两部分，满足部分放在destTureBeg, 不满足部分放在destFalseBeg。

当仅仅需要复制满足谓词的元素用copy_if()，复制不满足谓词的部分用remove_copy_if()。

线性复杂度。