首页 > 编程语言 > 详细

【算法】合并排序

时间:2015-04-11 20:52:44      阅读:269      评论:0      收藏:0      [点我收藏+]
#include <STDIO.H>
#include <STDLIB.H>

void mergePass(int *ar,int *pr,int s,int size);
void merge(int *ar,int *pr,int l,int m,int r);

void mergeSort(int *ar,int size)      // 合并排序
{
	int *pr=(int *)malloc(sizeof(int)*size);        //动态开辟要排序数组大小的一个新数组
	int s=1;  
	while(s<size)
	{
		mergePass(ar,pr,s,size);      //在一个while里执行两次mergerPass函数,目的是 执行完循环 使排序好的元素能保存到原来数组中
		s+=s;
		mergePass(pr,ar,s,size);
		s+=s;
	}
	free(pr);                  //函数执行完释放内存 避免内存泄露
}



void mergePass(int *ar,int *pr,int s,int size)  //函数的意义是合并给定大小s的相邻子数组
{
	int i=0,j=0;
	while(i <= size-2*s)         //保证 剩余未排序的元素个数 是小于2*s的
	{
		merge(ar,pr,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
	if(i+s<size)              //给i加上s 后仍然小于总长度,说明i后面元素个数大于等于s个(下标从0开始),所以可排序
	{
		merge(ar,pr,i,i+s-1,size-1);
	}
	else 
		for(j=i;j<size;j++)  //小于s个元素,直接保存到 目标数组
		{
			pr[j]=ar[j];
		}
}

void merge(int *ar,int *pr,int l,int m,int r)//函数的意义是 把ar[l]-ar[m]  和ar[m+1]-ar[r]  两个相邻子数组按大小顺序合并到pr这个数组中
{
	int i=l,
		j=m+1,
		k=l,
		t=0;

		while(i<=m && j<=r)     //比较后转移到目标数组。
		{
			if(ar[i]<ar[j])    //按从小到大的顺序
				pr[k++]=ar[i++];
			else 
				pr[k++]=ar[j++];
		}

		if(i>m)         //处理未判断的元素
			for(t=j;t<=r;t++)
				pr[k++]=ar[t];
		else 
			for(t=i;t<=m;t++)
				pr[k++]=ar[t];
}



int main()
{
	int ar[]={2,4,1,8,6,7,5,9,10,3};
	int i;
	mergeSort(ar,sizeof(ar)/sizeof(*ar));

	for(i=0;i<sizeof(ar)/sizeof(*ar);i++)
	{
		printf("%d ",ar[i]);
	}
	puts("");
}
技术分享

【算法】合并排序

原文:http://blog.csdn.net/a781558066/article/details/44998443

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!