C++中的 sort函数、函数指针、仿函数
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> inline
-
void 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 sort
-
template<class _RanIt> inline
-
void sort(_RanIt _First, _RanIt _Last)
-
{ // order [_First, _Last), using operator<
-
_STD sort(_First, _Last, less<>());
-
}
可以看出，默认的比较函数就是less<>()
再附上其中_Sort函数的代码：
-
template<class _RanIt,
-
class _Diff,
-
class _Pr> inline
-
void _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 quicksort
-
pair<_RanIt, _RanIt> _Mid =
-
_Unguarded_partition(_First, _Last, _Pred);
-
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
-
-
if (_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)
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/104823002
- 点赞
- 收藏
- 关注作者
评论（0）