e夜星空
C++,你看重C还是++?
posts - 1,comments - 0,trackbacks - 0
STL算法sort需要#include <algorithm>,它是重载的两个函数:
一个版本只有起止位置的迭代器,另一版本还有第3个参数用于比较,原型如下:
版本1:
template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last);
版本2:
template <class _RandomAccessIter, class _Compare>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
                 _Compare __comp);

函数的实现过程:判断如果__first == __last则结束,否则执行以下步骤:
调用__introsort_loop()对__first到__last间元素进行预排序;
调用__final_insertion_sort()进行最终排序。
关于这两个辅助函数的解剖是后话。

现在来看一下2参数版本与3参数版本的差别:
不同版本的sort只是调用不同版本的__introsort_loop()和__final_insertion_sort()函数,
3参数版本的sort把第3个参数直接传递给了它调用的函数,
如此罢了。

sort排序的结果是按照升序排列,前面元素的先于后面的元素,
如果两个值等价,那么sort并不严格保证它们的先后顺序。
(关于等值和等价可简单说:从1到10,它们值各不同,但现在6以下算一档,其余一档,那么1到5都等价)。
体现等价关系的是sort的第3个参数,2参数版本的sort默认为less<T>(小于)。
要保证元素间稳定的先后顺序需要使用stable_sort算法。

sort函数使用的条件为
两个迭代器必须是随机迭代器且不能为const,迭代器指向的元素类型必须有<运算符且迭代器类型必须是弱序的(关于弱序可参考http://www.sgi.com/tech/stl/LessThanComparable.html)。
3参数版本中还要求比较的函数对象是弱序的。

算法复杂度总是(最佳和最坏情形相同)O(N.logN),其中N为元素个数__last - __first。
早期的sort算法采用C语言的quicksort算法,那时最坏情形算法复杂度为O(N*N)平均为O(N.logN)。
现在sort算法都使用了Introspective排序算法。
the Art of Computer Programming. Volume 3: Sorting and Searching》和《Software Practice and Experience》分别介绍这两种算法。

posted on 2005-12-15 11:01 风之簸萝 阅读(875) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理