大家好，又见面了，我是全栈君。
本文为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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/115937.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
