C语言实现递归排序

思路

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

举例

如上图所示。

代码实现

//归并排序 
//将给定的数分成两个子数组——>一直到分成单位为2的子数组
//对子数组进行排序
//合并成原来长度的父数组 
#include<stdlib.h>
void sort(int a[],int len)
{
	void merge(int a[], int L[], int R[], int l, int r); 
	if(len>1)
	{
		int mid=len/2;
		int *L=(int *)malloc(sizeof(int)*mid);//定义俩数组 
		int *R=(int *)malloc(sizeof(int)*(len-mid));// 来存放子数组
		for(int i=0;i<mid;i++)
		{
			L[i]=a[i];//把左半部分放到L数组 
		} 
		for(int j=mid;j<len;j++)
		{
			R[j-mid]=a[j];//把右半部分放到R数组 
		} 
		sort(L,mid);//继续分 继续归并 （分成单位为2的子数组左右为1单位） 
		sort(R,len-mid); //进行merge函数 
	  	merge(a,L,R,mid,len-mid);//排序+合并函数
		free(L);
		free(R); 
	}
 } 
 void merge(int a[],int L[],int R[],int l,int r) 
 {
 	int i=0,j=0,k=0;
 	while(i<l&&j<r)//比较子串第一个数的大小  开始比较单位为1的子串
 	{//放到上一级父串
	  if(L[i]<=R[j])
	  {
	  	a[k++]=L[i++];//此时的a是上一级的父串
		}
		else
		{
			a[k++]=R[j++];
		}
	 }
	 while(i<l)//把比较完剩下的数放到上一级父串后面
	 {
	 	a[k++]=L[i++];
	 }
	 while(j<r)
	 {
	 	a[k++]=R[j++];
	 } 
 }

代码内的解释已经很详细，如果还有不懂得地方可以在下面提问，也欢迎大佬指点。