归并排序详解

文章目录

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

稳定性

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

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

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

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

归并排序

递归版

#include<stdio.h>

#include<stdlib.h>

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]<a[begin2])
{
tmp[i++]=a[begin1];
begin1++;
}
else
{
    tmp[i++]=a[begin2];
    begin2++;
}
}
//不知道谁结束了
while(begin1<=end1)
{
    tmp[i++]=a[begin1];
begin1++;
}
while(begin2<=end2)
{
   tmp[i++]=a[begin2];
    begin2++; 
}
//tmp还要拷贝回a，这样才可以回去进行归并
for(int j=left;j<=right;j++)
{
    a[j]=tmp[j];
}

}



void mergesort(int *a,int n)
{

    int *tmp=(int *)malloc(sizeof(int)*n);
    if(tmp==NULL)
    {
printf("malloc fail");
    return;
    }
_mergesort(a,0,n-1,tmp);//在这里容易递归，子函数
free(tmp);
tmp=NULL;

}

```c
在这里插入代码片

非递归版本

版本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)
   {
   for(int i=0;i<n;i+=2*gap)
   {
//这个循环里面就变成归并
//[i,i+gap-1],[i+gap,i+2*gap-1]
//[0,     0 ],[1    , 1       ]
int index=i;//tmp数组的起始位置是i相当于递归里面的left

int begin1=i,end1=i+gap-1;
int begin2=i+gap,end2=i+gap*2-1;
//如果个数为奇数的话
//第一组越界,end1越界，【begin2,end2】不存在
if(end1>=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]<a[begin2])
    {
        tmp[index++]=a[begin1++];
    }
else
{

    tmp[index++]=a[begin2++];
}

}
while(begin1<=end1)
{
    tmp[index++]=a[begin1++];
}
while(begin2<=end2)
{
     tmp[index++]=a[begin2++];
}

}
//把归并数组拷贝回原数组
//整段拷贝回去
for(int i=0;i<n;i++)
{
    a[i]=tmp[i];
}
gap*=2;
   }

free(tmp);//解决了tmp的溢出问题
tmp=NULL;

   }

版本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)
   {
   for(int i=0;i<n;i+=2*gap)
   {
//这个循环里面就变成归并
//[i,i+gap-1],[i+gap,i+2*gap-1]
//[0,     0 ],[1    , 1       ]
int index=i;//tmp数组的起始位置是i相当于递归里面的left

int begin1=i,end1=i+gap-1;
int begin2=i+gap,end2=i+gap*2-1;

//end1越界 或者 begin2都不需要处理归并，
if(end1>=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]<a[begin2])
    {
        tmp[index++]=a[begin1++];
    }
else
{

    tmp[index++]=a[begin2++];
}

}
while(begin1<=end1)
{
    tmp[index++]=a[begin1++];
}
while(begin2<=end2)
{
     tmp[index++]=a[begin2++];
}
for(int j=begin1;j<=end1;j++)
{
    a[j]=tmp[j];
}
}
//把归并数组拷贝回原数组
//整段拷贝回去

gap*=2;
   }

free(tmp);
tmp=NULL;

   }

void print(int *a,int n)
{
    int i=0;
    for(i=0;i<n;i++)
    {
printf("%d ",a[i]);

    }
}



int main()
{
    //归并排序
    int arr[10]={10,6,7,1,3,4,2,0,11,12};
    //mergesort(arr,sizeof(arr)/sizeof(int));
   // mergesortnonr(arr,sizeof(arr)/sizeof(int));
    mergesortnonr2(arr,sizeof(arr)/sizeof(int));
    print(arr,sizeof(arr)/sizeof(int));
    return 0;
}