归并排序详解

• 稳定性
• 归并排序
• • 递归版
  • 非递归版本
  • • 版本1
    • 版本2

稳定性：保持相对位置不变

冒泡排序，归并排序，直接插入排序的具有稳定性，在排序的时候不会改变数据的相对位置

快速排序，希尔排序，选择排序都不具有稳定性

综合比较之下快速排序的效率最高，在大多面试时候也多以快速排序，堆排序，归并排序为主

#include

#include

void _mergesort(int *a,int left,int right,int *tmp)
{
//1个就不用分了
if(left>=right)

{
    return;
}

int mid=(left+right)/2;

//[left,mid]有序[mid+1,right],有序就可以进行归并了
//左边和右边都有序了就可以进行归并了

_mergesort(a,left,mid,tmp);
_mergesort(a,mid+1,right,tmp);
//后序
//开始归并了
int begin1=left,end1=mid;
int begin2=mid+1,end2=right;
int i=left;//i不是0而是left，这样返回原数组就可以
while(begin1<=end1&&begin2<=end2)//有一个结束了就可以把另一个全部都接起来
{
if(a[begin1] 
非递归版本 
版本1 
//归并非递归循环写法
void mergesortnonr(int *a,int n)//n为个数
{
 int *tmp=(int *)malloc(sizeof(int)*n);
    if(tmp==NULL)
    {
printf("malloc fail");
    return;
    }
   
   int gap=1;//一个一个归，gap作为归并的间距
  
   while(gap=n)//等于n就已经越界了//先end1
{
    end1=n-1;//进行修正
}

//第2组不存在,begin2,end2不存在，再被begin2
if(begin2>=n)
{
    //让这个区间不存在，就不用对这个区间进行操作了
    begin2=n;
    end2=n-1;

}

if(end2>=n)//begin2存在，区间存在就修正为n-1
{
    end2=n-1;//再修正一下
}
//如果begin1=end1=begin2=end2=n-1的话，tmp就会越界，重复的index++，后free多的未开辟的空间，index越界，进取一次出来又一次+


//将其进行归并
while(begin1<=end1&&begin2<=end2)
{
    if(a[begin1] 
版本2 
void mergesortnonr2(int *a,int n)//n为个数
{
 int *tmp=(int *)malloc(sizeof(int)*n);
    if(tmp==NULL)
    {
printf("malloc fail");
    return;
    }
   
   int gap=1;//一个一个归
  
   while(gap=n||begin2>=n)
{
     break;//进行修正
}
//end2越界就需要归，就修正end2就可以
if(end2>=n)
{
    end2=n-1;//再修正一下
}
//如果begin1=end1=begin2=end2=n-1的话，tmp就会越界，重复的index++，后free多的未开辟的空间，index越界，进取一次出来又一次+


//将其进行归并
while(begin1<=end1&&begin2<=end2)
{
    if(a[begin1] 
void print(int *a,int n)
{
    int i=0;
    for(i=0;i