归并排序（递归、非递归）

2025/4/19 6:20:38 来源：https://blog.csdn.net/LXdian_LX/article/details/147326177 浏览: 次关键词：归并排序（递归、非递归）

归并排序

递归实现归并排序

今天讲讲归并排序，啥也不说了，大家看图吧：

动图：

在这里插入图片描述

静态图：
在这里插入图片描述

来，我说不明白的，让AI来讲：

在这里插入图片描述

所以归并排序的缺点也很明显了，空间复杂度高，需要开一个相同大小的数组。归并的时候，就归并到新数组去，然后再复制到原数组。

了解思想之后就开始写代码：

sort.h

#include <stdio.h>
#include <stdlib.h>
#include <string.h>void PrintArray(int *a,int n);void _MergeSort(int *a,int *b,int begin,int end);
void MergeSort(int *a,int n);

sort.c

#include "sort.h"void PrintArray(int *a,int n)
{for(int i=0;i<n;i++){printf("%d ",a[i]);}printf("\n");
}void _MergeSort(int *a,int *b,int begin,int end)
{if (begin >= end)return;int mid=(end+begin)/2;_MergeSort(a,b,begin,mid);_MergeSort(a,b,mid+1,end);int begin1=begin,end1=mid;int begin2=mid+1,end2=end;int index=begin;while (begin1<=end1 && begin2<=end2){if(a[begin1]<=a[begin2]){b[index++]=a[begin1++];}else{b[index++]=a[begin2++];}}while(begin1<=end1){b[index++]=a[begin1++];}while(begin2<=end2){b[index++]=a[begin2++];}memcpy(a+begin,b+begin,(end-begin+1)* sizeof(int));}
void MergeSort(int *a,int n)
{int *b=(int *) malloc(sizeof(int)*n);if(b==NULL){perror("malloc failed");return;}_MergeSort(a,b,0,n-1);free(b);
}

main.c

#include "sort.h"void Test()
{int a[]={10,6,7,1,3,9,4,2,5,8};MergeSort(a, sizeof(a)/ sizeof(int));PrintArray(a, sizeof(a)/ sizeof(int));
}int main()
{Test();return 0;
}

在这里插入图片描述

非递归实现归并排序

通过上文的解析呢，其实也可以看的出来，我们递归的主要作用就是用来分解数组了，把数组分成一个个小区间，当递归分解到区间大小只有1的时候就开始归并，这样大小为2的区间也有序了，然后一直往上归并。

也就是说，递归实现是从原数组开始分解，分解完成之后往回归并。

那么这里的非递归实现归并排序，我们就直接从小区间开始，我们直接从已经分解好的开始，直接开始归并。这样就不用去递归了。

在这里插入图片描述

void MergeSortNonR(int *a,int n)
{int *b=(int *) malloc(sizeof(int)*n);if(b==NULL){perror("malloc failed");return;}int gap=1;while(gap<n){for(int i=0;i<n;i+=2*gap){int begin1=i,end1=i+gap-1;int begin2=i+gap,end2=i+2*gap-1;int index=i;if(begin2>=n){break;}if(end2>=n){end2=n-1;}while (begin1<=end1 && begin2<=end2){if(a[begin1]<=a[begin2]){b[index++]=a[begin1++];}else{b[index++]=a[begin2++];}}while(begin1<=end1){b[index++]=a[begin1++];}while(begin2<=end2){b[index++]=a[begin2++];}//复制memcpy(a+i,b+i,(end2-i+1)* sizeof(int));}gap*=2;}free(b);
}