C++中的 sort函数、函数指针、仿函数

举报
用户已注销 发表于 2021/11/19 04:28:04 2021/11/19
【摘要】 sort函数有2种常见的写法,一种是不带参的,也就是默认的升序,一种是传入函数指针的,用函数自定义排序规则。 示例: #include<iostream>#include<algorithm>#include<functional>using namespace std; class cmp{pu...

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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。