数据结构之---C语言实现归并排序

//归并排序
//杨鑫
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
int N, i;
int a[MAXN];
void merge(int a[], int p, int q, int r)
{
	int i, j,  k, n1, n2;
	int *front, *back;
  	n1 = q - p + 1;            //前一部分的长度
	n2 = r-q;                  //后一部分的长度
	front = (int *) malloc (n1 * sizeof(int));
	back  = (int *) malloc (n2 * sizeof(int));
	for(i = 0; i < n1; i++)
			front[i] = a[p + i];
	for(i = 0; i < n2; i++)
			back[i] = a[q + 1 + i];
	//合并元素
	i = 0, j = 0, k= p;
	while(i < n1 && j < n2)
	{
		if(front[i] < back[j])
		{
			a[k++] = front[i++];
		}
		else
		{
			a[k++] = back[j++];
		}
	}
	//将剩余的元素合并
	while(i < n1)
	{
		a[k++] = front[i++];
	}
	while(j < n2)
	{	
		a[k++] = back[j++];
	}
}
void merge_sort(int a[], int p, int r)
{
	int q;
	if(p < r)
	{
		q = (p + r)/2;
		merge_sort(a, p, q);
		merge_sort(a, q + 1, r);
		merge(a, p, q, r);
	}
}
int main()
{
	printf("===================归并排序=============\n\n");
	printf("请输入将要排序元素的个数！\n");
	scanf("%d", &N);
	printf("请分别输入 %d 个元素\n", N);
	for(i=0; i < N; i++)
	{
		scanf("%d", &a[i]);
	}
	merge_sort(a, 0, N-1);
	printf("\n排序后的元素是:\n");
	for(i = 0; i < N; i++)
		printf(" %d", a[i]);
	return 0;
}