STL的Sort排序(1)

时间:2022-01-17 04:17:01

STL的sort函数:
sort(begin,end,less) //全排序
stable_sort(begin,end,less)//全排序,且相等的两个元素保持前后顺序不变
partial_sort(begin,begin+3,end,less)//部分排序

 

sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排
序算法)。注1,可以保证很好的平均性能、复杂度为n*log(n),由于单纯的快速排序在理论上有最差的情
况,性能很低,其算法复杂度为n*n,但目前大部分的STL版本都已经在这方面做了优化,因此你可以放心
使用。stable_sort采用的是"归并排序",分派足够内存是,其算法复杂度为n*log(n), 否则其复杂度为
n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。

 

sort 和 stable_sort都没有指定比较函数,系统会默认使用operator< 对区间[first,last)内的所有元素进行排序, 因此,如果你使用的类型义军已经重载了operator<函数,那么你可以省心了。如果没有,你可以随意指定比较函数,应用更为灵活一些。