stl排序总结.doc

学习网站：/twiki/bin/view.pl/Main/STLTechArticles ?????????????????? /twiki/bin/view.pl/Main/STLSortAlgorithms 排序(sort)：所有sort算法介绍:使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator) 1.????? 所有STL sort算法函数的名字列表: 函数名 功能描述 sort 对给定区间所有元素进行排序 stable_sort 对给定区间所有元素进行稳定排序 partial_sort 对给定区间所有元素部分排序 partial_sort_copy 对给定区间复制并排序 nth_element 找出给定区间的某个位置对应的元素 is_sorted 判断一个区间是否已经排好序 partition 使得符合某个条件的元素放在前面 stable_partition 相对稳定的使得符合某个条件的元素放在前面 ? 2.????? 比较函数：当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数。 vector int vect; //... sort(vect.begin(), vect.end()); //此时相当于调用 sort(vect.begin(), vect.end(), lessint() ); sort 中的其他比较函数 equal_to 相等 not_equal_to 不相等 less 小于 greater 大于 less_equal 小于等于 greater_equal 大于等于 上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表: 不能直接写入仿函数的名字，而是要写其重载的()函数： lessint(); 当你的容器中元素时一些标准类型（int float char)或者string时，你可以直接使用这些函数模板。但如果你 时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的操作赋。如： bool less_second(const myclass m1, const myclass m2) { ??????? return m1.second m2.second; } ? 3.????? 全排序：全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的快速排序算法(目前大部分STL版本已经不是采用简单的快速排序，而是结合内插排序算法)。复杂度为n*log(n).stable_sort采用的是归并排序，分派足够内存是，其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n)，其优点是会保持相等元素之间的相对位置在排序前后保持一致。 用于全排序的函数有： void sort(RandomAccessIterator first, RandomAccessIterator last); void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp); void stable_sort(RandomAccessIterator first, RandomAccessIterator last); void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp); 4.????? 局部排序：partial_sort采用的堆排序（heapsort），它在任何情况下的复杂度都是n*log(n). 局部排序其实是为了减少不必要的操作而提供的排序方式。 其函数原型为： 1)????? void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last); 2)????? void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,???????? RandomAccessIterator last, StrictWeakOrdering comp); 3)????? RandomAccessIterator partial_sort_co