C语言实现归并排序_归并排序c语言实现

知识准备

将多个有序表整合成一个有序表
思路：开始两个两个元素进行比较形成新的子表，然后含有两个元素的子表于另一个子表进行比较，形成四个元素的子表，以此类推，最终形成只有两个子表，再归并，形成有序序列。

#include <stdio.h>
#include <stdlib.h>
#define n 7

int *temp=(int*)malloc(n*sizeof(int));
void MergeSortEle(int Ele[],int low,int high);
void Merge(int Ele[],int low,int mid,int high);
int main ()
{
	int i;
	int date[]={49,38,65,97,76,13,27};
	int len=sizeof(date)/sizeof(date[0]);

	MergeSortEle(date,0,len-1);
	for(i=0;i<len;i++)
	{
	//	printf("%d\n",date[i]);
	}
	return 0;

}
void MergeSortEle(int Ele[],int low,int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		MergeSortEle(Ele,low,mid);
		MergeSortEle(Ele,mid+1,high);
		Merge(Ele,low,mid,high);

	}
}

void Merge(int Ele[],int low,int mid,int high)
{
	//存放在一个子数组中temp，进行中转
	int k,m;
	for(k=low;k<=high;k++)
	{
		temp[k]=Ele[k];
		printf("-%d",Ele[k]);
	}

	printf("\n");
	//进行归并排序
	int i,j,l;
	for(i=low,j=mid+1,l=i;i<=mid&&j<=high;l++)
	{
		if(temp[i]<=temp[j])
		{
			Ele[l]=temp[i++];
		}else
		{
			Ele[l]=temp[j++];
		}
	}
	while(i<=mid)Ele[l++]=temp[i++];
	while(j<=high)Ele[l++]=temp[j++];
	for(m=0;m<=high;m++)
	{
		printf("$%d",Ele[m]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

归并过程：

手动递归过程：