【C语言】归并排序

一、算法描述

•  用递归算法把一个数组拆成两份，直到拆成一份一份的
• 在递归算法里添加一个函数，能把两个有序数组合并成为一个有序数组
• 直到完成递归

二、归并排序代码

三、测试代码

#include<stdio.h>
 
void merge(int a[],int left,int right,int mid) {
	int lenth = right-left+1;
	int temp[lenth];
	int i = left, j = mid + 1,k = 0;
	while (i <= mid && j <= right) {
		if (a[i] < a[j]) {
			temp[k++] = a[i++];
		}
		else {
			temp[k++] = a[j++];
		}
	}
	while (i <= mid) temp[k++] = a[i++];
	while (j <= right)  temp[k++] = a[j++];
	k = 0;
	while (k<lenth) {
		a[k+left] = temp[k];
		k++;
	}
}
 
void merge_sort(int a[],int left,int right){
	if(left<right){
		int mid = (left + right) / 2;
		merge_sort(a,left, mid);
		merge_sort(a, mid + 1, right);
		merge(a, left, right, mid);
	}
}
 
int main()
{
	int n,i;
	printf("请输入需要排序的数的个数：\n");
	scanf("%d",&n);
	int a[n];
	printf("请输入需要排序的数：\n");
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	merge_sort(a,0,n-1);
	printf("归并排序的结果：\n");
	for(i=0;i<n;i++)
		printf("%d ",a[i]);
}