欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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 ;
}