Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

绿色网站无广告
会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

再写_归并排序

来源: Kay_Sprint 分享至:

还是觉得武大教授写的数据结构的书比较适合我,想法比较接近,易懂。看回暑假写的归并排序,真的是一头雾水,看看书什么的,也讲得不怎么样,下面这个是我自己最喜欢的一个版本。

#include <iostream>
using namespace std;

void Merge(int r[],int low,int mid,int high)
{
	//将两个有序表直接归并为一个有序表
	//每次归并完都将结果保存回原数组中
	int *r1;
	int i=low,j=mid+1,k=0;
	r1=new int[high-mid+1];
	while(i<=mid && j<=high)
	{
		if(r[i]<=r[j])
		{
			r1[k]=r[i];
			i++;
			k++;
		}
		else
		{
			r1[k]=r[j];
			j++;
			k++;
		}
	}
	while(i<=mid)
	{
		r1[k]=r[i];
		i++;
		k++;
	}
	while(j<=high)
	{
		r1[k]=r[j];
		j++;
		k++;
	}
	for(k=0,i=low;i<=high;i++,k++)
		r[i]=r1[k];
}

					//自底向上归并排序

//在某趟归并排序中设各子表长度为length(最后一个子表长度可能小于length)
//则归并数组r[0,...,n-1]的前(n+1)/length个有序子表:r[0...length-1]、
//r[length...2*length-1],....,r[((n+1)/length)...n-1].调用merge函数将相邻
//的一对子表进行归并时,要考虑到一些特殊情况:若子表的个数为奇数,那么最后
//一个子表无需和其他子表进行归并(即那趟归并不做);若子表个数为偶数,那么要
//注意最后一对子表的后一个子表的区间上限是n-1.

void Merge_Pass(int r[],int length,int n)
{
	//对整个序列进行一趟归并
	int i;
	for(i=0;i+2*length-1<n;i+=2*length)  //归并长度为length的两个子表
		Merge(r,i,i+length-1,i+2*length-1);
	if(i+length-1 < n)   //归余下两个子表,后者长度小于length
		Merge(r,i,i+length-1,n-1);  //归并两子表
}

//自底向上的基本思想是:第一趟归并排序时,将待排序表r[0,...,n-1]看作是
//n个长度为1的有序子表,将这些子表两两归并,若n为偶数,则得到n/2个长度为
//2的有序子表,若n为奇数,则最后一个子表不参与归并,一趟归并完成后,前
//n/2个子表是长度为2的有序子表,最后一个子表的长度为1.第二趟是将第一趟归并
//好的有序子表再进行两两归并,如此反复,直到最后得到一长度为n的子表。
//因为都是两两归并,所以也叫2路归并,类似的还有k(k>2)路归并

void Merge_Sort_1(int r[],int n)
{
	int length;
	for(length=1;length<n;length*=2) //进行log2(n)趟归并
		Merge_Pass(r,length,n);
}

				//自顶向下归并排序

//自顶向下归并排序的思想是:将当前区间r[low,...high]一分为二,即
//求mid=(low+high)/2,递归对两个区间r[low,..,mid]和r[mid+1,...,high]
//持续分解,终止条件是每个子区间的长度为1(只有一个记录的子表一定是有序表)
//在分解完之后就是归并,归并的过程和分解的相反,就是将两个子区间归并为一个
//有序的区间

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

void Merge_Sort_2(int r[],int n)
{
	Merge_SortDC(r,0,n-1);
}

int main()
{
	int a[7]={23,54,254,5234,56,6,11};
	cout<<"自底向上归并排序"<<endl;
	cout<<endl;
	Merge_Sort_1(a,7);
	for(int i=0;i<7;i++)
		cout<<a[i]<<"  ";
	cout<<endl;

	cout<<endl;
	int a2[7]={23,54,254,5234,56,6,11};
	cout<<"自顶向下归并排序"<<endl;
	cout<<endl;
	Merge_Sort_2(a2,7);
	for(i=0;i<7;i++)
		cout<<a2[i]<<"  ";
	cout<<endl;
	cout<<endl;

	return 0;
}

测试结果

自底向上归并排序

6  11  23  54  56  254  5234

自顶向下归并排序

6  11  23  54  56  254  5234

Press any key to continue



Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史