C++实现归并排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++实现归并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1283字，纯文字阅读大概需要2分钟。

内容图文

文章目录

• 归并排序
• 实例演示
• 代码实现
• 结果展示
• 归并排序的特性总结：

---

归并排序

基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

实例演示

代码实现

#include<iostream>
using namespace std;
#include<vector>


void _MergeSort(vector<int>& a,int begin,int end,vector<int>& tmp)
{
    if(begin>=end)
    return;
    int mid=(begin+end)>>1;
    _MergeSort(a,begin,mid,tmp);
    _MergeSort(a,mid+1,end,tmp);

    int begin1=begin,end1=mid;
    int begin2=mid+1,end2=end;
    int index=begin;
    while(begin1<=end1&&begin2<=end2)
    {
        if(a[begin1]<a[begin2])
        tmp[index++]=a[begin1++];
        else
        tmp[index++]=a[begin2++];
    }
    if(begin1<=end1)
    {
        while(begin1<=end1)
        tmp[index++]=a[begin1++];
    }
    if(begin2<=end2)
    {
        while(begin2<=end2)
        tmp[index++]=a[begin2++];
    }
    a=tmp;
}
void MergeSort(vector<int>& a,int n)
{
    vector<int> tmp(a);
    _MergeSort(a,0,n-1,tmp);
}
int main()
{
	int n;
	cin >> n;
	vector<int> a;
	while (n--)
	{
		int k;
		cin >> k;
		a.push_back(k);
	}
	MergeSort(a, a.size());
	for (auto e : a)
	{
		cout << e << " "; 
	}
    system("pause");
	return 0;
}

结果展示

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

内容总结

以上是互联网集市为您收集整理的C++实现归并排序全部内容，希望文章能够帮你解决C++实现归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---