首页 > 代码库 > STL 源码剖析 算法 stl_algo.h -- merge sort

STL 源码剖析 算法 stl_algo.h -- merge sort

本文为senlie原创,转载请保留此地址:http://blog.csdn.net/zhengsenlie


merge sort

----------------------------------------------------------------------



描述:归并排序
思路:
1.将区间对半分割
2.对左、右段分别排序
3.利用inplace_merge将左、右段合并成为一个完整的有序序列


复杂度:O(nlog n)
源码:
template<class BidirectionalIter>
void mergesort(BidirectionalIter first, BidirectionalIter last){
	typename iterator_traits<BidirectionalIter>::diference_type n = distance(first,last);
	if(n == 0 || n == 1) return ;
	else{
		BidirectionalIter mid = first + n / 2;
		mergesort(first, mid);
		mergesort(mid, last);
		inplace_merge(first, mid, last);
	}
}


示例:

int main()
{

	int a[]={3,8,0,6,7,4,2,1,9,3,1,8,3,9,2,0,9};
	int *a_end=a+sizeof a/sizeof(int);
	

	std::cout<<"a before mergesort: ";
	std::for_each(a, a_end, print<int>);
	std::cout<<'\n';

	mergesort(a, a_end);

	std::cout<<"a after mergesort: ";
	std::for_each(a, a_end, print<int>);
	std::cout<<'\n';

	return 0;
}