蓝桥杯中的合并排序问题

浏览数：25 / 时间：2015年06月08日

/*题目内容：
使用合并排序算法，对输入的n个数据进行按升序排序。
输入描述
分两行，第一行是整数n,第二行是n个整数，每个整数之间用空格间隔。

输出描述
按升序排序的n个整数

输入样例
8
9 8 7 6 5 4 3 2

输出样例
2 3 4 5 6 7 8 9*/

/*分析：合并排序中用到了分治，其中比较关键的两个部分是1：合并分组排序的递归2：将排序后的小数组合并

#include<stdio.h>
#define M 100

void Merge(int a[],int b[],int start,int mid,int last)
{
	int i = start,j = mid + 1,k = 0;
	while(i <= mid&&j <= last)
	{
		if(a[i] < a[j])
			b[k++] = a[i++];
		if(a[i] > a[j])
			b[k++] = a[j++];
	}
	while(i <= mid)//在分组长度不一致时保证所有元素都进入数组b中
	{
		b[k++] = a[i++];
	}
	while(j <= last)//在分组长度不一致时保证所有元素都进入数组b中
	{
		b[k++] = a[j++];
	}
	for(i = 0;i < k; i++)
		a[start + i] = b[i];
}

void MergeSort(int a[],int b[],int start,int last)
{
	int mid;
	if(start < last)
	{
		mid = (start + last)/2;
		MergeSort(a,b,start,mid);
		MergeSort(a,b,mid + 1,last);
		Merge(a,b,start,mid,last);
		//Copy(a,b,start,last);
	}
}

int main()
{
	int num,array[M],b[M];
	int i;
	scanf("%d",&num);
	for(i = 0;i < num; i++)
		scanf("%d",&array[i]);
	MergeSort(array,b,0,num - 1);
	for(i = 0;i < num; i++)
		printf("%d ",array[i]);
	return 0;
}

补充一句：合并排序的时间复杂度是O(nlogn)

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

蓝桥杯中的合并排序问题