sort函数有2种常见的写法,一种是不带参的,也就是默认的升序,一种是传入函数指针的,用函数自定义排序规则。
示例:
#include<iostream>#include<algorithm>#include<functional>using namespace std;class cmp{public:bool operator()(int a, int b) //从小到大{return a < b;}};bool cmp2(int a, int b) //从大到小{return a > b;}int main(){int num[4] = { 1, 3, 4, 2 };sort(num, num + 4);cout << num[0] << num[1] << num[2] << num[3] << endl;sort(num, num + 4, cmp2);cout << num[0] << num[1] << num[2] << num[3] << endl;sort(num, num + 4, cmp());cout << num[0] << num[1] << num[2] << num[3] << endl;sort(num, num + 4, greater<>());cout << num[0] << num[1] << num[2] << num[3] << endl;sort(num, num + 4, less<>());cout << num[0] << num[1] << num[2] << num[3] << endl;return 0;}输出:
1234
4321
1234
4321
1234
其中,sort(num, num + 4);是默认的升序排序,
sort(num, num + 4, cmp2); 是传入cmp2这个函数指针,
而sort(num, num + 4, c); 是传入一个对象,对象中包含一个仿函数。
greater<>() 和 less<>() 都是头文件<functional>中的函数。
仿函数,就是在类中重载()运算符,使得一个类表现得像一个函数。
C++中的sort函数由于用了模板编程,使得用处非常广泛,而且时间复杂度是O(n log n),效率也很高。
附上C++中sort的实现代码:
template<class _RanIt,class _Pr> inlinevoid sort(_RanIt _First, _RanIt _Last, _Pr _Pred){// order [_First, _Last), using _Pred_DEBUG_RANGE(_First, _Last);_DEBUG_POINTER(_Pred);_Sort(_Unchecked(_First), _Unchecked(_Last), _Last - _First, _Pred);}// TEMPLATE FUNCTION sorttemplate<class _RanIt> inlinevoid sort(_RanIt _First, _RanIt _Last){// order [_First, _Last), using operator<_STD sort(_First, _Last, less<>());}可以看出,默认的比较函数就是less<>()
再附上其中_Sort函数的代码:
template<class _RanIt,class _Diff,class _Pr> inlinevoid _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred){// order [_First, _Last), using _Pred_Diff _Count;for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; ){// divide and conquer by quicksortpair<_RanIt, _RanIt> _Mid =_Unguarded_partition(_First, _Last, _Pred);_Ideal /= 2, _Ideal += _Ideal / 2;// allow 1.5 log2(N) divisionsif (_Mid.first - _First < _Last - _Mid.second){// loop on second half_Sort(_First, _Mid.first, _Ideal, _Pred);_First = _Mid.second;}else{// loop on first half_Sort(_Mid.second, _Last, _Ideal, _Pred);_Last = _Mid.first;}}if (_ISORT_MAX < _Count){// heap sort if too many divisions_STD make_heap(_First, _Last, _Pred);_STD sort_heap(_First, _Last, _Pred);}else if (1 < _Count)_Insertion_sort(_First, _Last, _Pred);// small}可以看出是快速排序、堆排序、插入排序三者的结合。
快速排序的优点是平均时间比堆排序快,但时间复杂度是O(n^2),而堆排序的时间复杂度是O(n log n)
这里的sort函数,平均排序时间非常快,而且时间复杂度是O(n log n)
3个排序的结合方法:
(1)深度太深时使用堆排序
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
这个注释不对,实际上应该是log(N)/log(4/3)次划分,大概等于2.4 log2(N)
_Ideal 这个量没有具体的含义,它既是一开始等于N,然后每次乘以3/4,当它变为0时我就当做深度太深,剩下的交给堆排序
(2)元素太少时使用插入排序
这里的常量_ISORT_MAX = 32,即当递归到只有32个元素时,对这个小片段采取插入排序。
片段花费时间32*31
如果N个元素分割成N/32个片段,每个片段都是32个元素,都采取插入排序,那么总时间是:
N/32 * 32*31 + N* log2(N/32) = N* (log2(N) +26)
这个结果可以认为就是N* log2(N)