C++归并排序
程序员文章站
2022-05-31 08:21:06
...
C++归并排序与快速排序一样都是利用分治算法的思想,所以复杂度均是O(nlogn)
#include <iostream>
#include<cstdio>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
//归并排序时间复杂度为O(nlogn)
void _sort(vector<int>&v,int begin,int end);
void merge_sort(vector<int>&v,int begin,int mid,int end);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
while(scanf("%d",&n)!=EOF)
{
vector<int>num(n);
for(int i=0;i<n;++i)
cin>>num.at(i);
_sort(num,0,n-1);
for(int i=0;i<num.size();++i)
cout<<num[i]<<" ";
cout<<endl;
//copy(num.begin(),num.end(),ostream_iterator<int,char>(cout," "));
}
return 0;
}
void _sort(vector<int>&v,int begin,int end)
{
if(begin<end)
{
int mid=(begin+end)/2;
_sort(v,begin,mid);
_sort(v,mid+1,end);
merge_sort(v,begin,mid,end);
}
return ;
}
void merge_sort(vector<int>&v,int begin,int mid,int end)//从小到大排列
{
vector<int>temp;
int l=begin,m=mid+1,r=end;
while(l<=mid&&m<=r)
{
if(v.at(l)<=v.at(m)) {temp.push_back(v.at(l));++l;}
else {temp.push_back(v.at(m));++m;}
}
while(l<=mid)
temp.push_back(v.at(l++));
while(m<=r)
temp.push_back(v.at(m++));
for(int i=0;i<temp.size();++i)
v.at(i+begin)=temp.at(i);//注意这里一定要从begin开始
return ;
}
上一篇: Linux系统下部署项目的设置方法