简要整理归并排序

由于最近写的题目中出现了一些排序算法,而自己又一时想不起来(可能是sort用太多了),所以准备整理一下归并排序和快速排序.
大部分资料来自慕课
归并排序:
归并排序运用了分治的思想,拥有较高的效率和稳定性.
时间复杂度为O(n)

归并排序的大致部分:
1.将数组分成前后两部分
2.分别排序前后两部分的数组
3.将已排序好的数组再归并回原数组
其中的难点就是如何归并.

首先将数组分成两部分排序

void MergeSort(int a[],int s,int e,int tmp[])//分别是待排序的数组,起始位置,结束位置,存放排序中间结果的数组 
{
	if(s<e)//如果s==e就没有比较的意义了,结束 
	{
		int m=s+(e-s)/2;//确定中间的下标,用(e-s)/2计算可以防止计算过程数值溢出
		MergeSort(a,s,m,tmp);//排序前部分 
		MergeSort(a,m+1,e,tmp);//后部分 
		Merge(a,s,m,e,tmp); //归并 
	}
}//递归的思路

核心部分,排序加归并(排序的时候同时归并)

void Merge(int a[],int s,int m,int e,int tmp[])
{//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,保证tmp有序,然后再拷贝回a[s,m]
 //归并的时间复杂度为O(n)
  int pb=0;//代表tmp结尾的指针 
  int p1=s;//指向前半段开头的指针 
  int p2=m+1;//指向后半段开头的指针 
  while(p1<=m&&p2<=e)//判断一段是否结束 
  {//判断指针代表的数,哪个小哪个先进
  	if(a[p1]<a[p2])//从小到大排序
  		tmp[pb++]=a[p1++];//每进入一个,则该指针加一 
	else
		tmp[pb++]=a[p2++];
  }
  //剩下的都是一个部分的
  while(p1<=m)
  	tmp[pb++]=a[p1++];
  while(p2<=e)
  	tmp[pb++]=a[p2++];
  for(int i=0;i<e-s+1;i++)//拷贝回原数组 
  	a[s+i]=tmp[i]; 	
}

大致流程:
简要整理归并排序

全部代码

#include<iostream>
using namespace std;
void Merge(int a[],int s,int m,int e,int tmp[])
{//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,保证tmp有序,然后再拷贝回a[s,m]
 //归并的时间复杂度为O(n)
  int pb=0;//代表tmp结尾的指针 
  int p1=s;//指向前半段开头的指针 
  int p2=m+1;//指向后半段开头的指针 
  while(p1<=m&&p2<=e)//判断一段是否结束 
  {//判断指针代表的数,哪个小哪个先进
  	if(a[p1]<a[p2])
  	{
  		tmp[pb++]=a[p1++];//每进入一个,则该指针加一 
	}else
	{
		tmp[pb++]=a[p2++];
	}
  }
  //剩下的都是一个部分的
  while(p1<=m)
  	tmp[pb++]=a[p1++];
  while(p2<=e)
  	tmp[pb++]=a[p2++];
  for(int i=0;i<e-s+1;i++)//拷贝回原数组 
  	a[s+i]=tmp[i]; 	
} 
void MergeSort(int a[],int s,int e,int tmp[])//分别是待排序的数组,起始位置,结束位置,存放排序中间结果的数组 
{
	if(s<e)//如果s==e就没有比较的意义了,结束 
	{
		int m=s+(e-s)/2;//确定中间的值,用(e-s)/2计算可以防止计算过程数值溢出
		MergeSort(a,s,m,tmp);//排序前部分 
		MergeSort(a,m+1,e,tmp);//后部分 
		Merge(a,s,m,e,tmp); //归并 
	}
}//递归的思路 
int main()
{
	int a[10]={13,27,19,2,8,12,2,8,30,89};
	int b[10];//中间数组 
	int size =sizeof(a)/sizeof(int);//计算大小
	MergeSort(a,0,size-1,b);
	for(int i=0;i<size;i++)
	{
		cout<<a[i]<<" ";
	} 
	cout<<endl;
	return 0;
}

以上就是归并排序的整理,每句代码都有注释,应该容易理解.
本文几乎所有资料来自慕课,初学者建议花时间去看下视频,效果更好.
链接:归并排序
(这是我的第一篇文章,可能有些不足,如果有什么好的建议欢迎评论)

简要整理归并排序

相关推荐