【算法导论】合并排序法-阿里云开发者社区

开发者社区> tengweitw> 正文

【算法导论】合并排序法

简介:        分治法:将原问题划分为n个规模较小而结构与原问题相似的子问题;递归地解决这些子问题,然后再合并其结果,就得到了原问题的解。分治法在每一个递归上都有三个步骤:分解、解决、合并。
+关注继续查看

       分治法:将原问题划分为n个规模较小而结构与原问题相似的子问题;递归地解决这些子问题,然后再合并其结果,就得到了原问题的解。分治法在每一个递归上都有三个步骤:分解、解决、合并。而在本文中的合并排序法正是运用了这种分而治之的策略:把一个n个元素的数组先分成两个数组,然后继续分下去,知道分成n个数组;然后将其逐一合并排序,最终得到排列好了的数组。下面我们首先看一看合并排序了原理框图:(图中黑色部分看不见不要紧,只需了解是将数组L、R中浅颜色的元素从小到大依次填入数组A中



上述原理的具体代码实现如下:

/***************************************
/              合并排序
/输入:数组arrayA、数组长度、p q r为数组下标
/输出:由小到大的数组
/时间复杂度:n
***************************************/

void Merge(int* arrayA,int p,int q,int r)
{
	int i=0;
	int j=0;
	int n1=q-p+1;//计算两个数组的长度
	int n2=r-q;//且这两个数组是已排列好的数组
	int arrayL[100]={0};//数组大小要大于n1
	int arrayR[100]={0};//数组大小要大于n2
	for(i=0;i<n1;i++)//对两个数组赋初值
		arrayL[i]=arrayA[p+i];
	    arrayL[i]=10000;//作为哨兵,判断是否到结尾
	for(i=0;i<n2;i++)   //也可以不用哨兵
		arrayR[i]=arrayA[q+i+1];
	    arrayR[i]=10000;

    i=0;j=0;
	for(int k=p;k<=r;k++)
	{
		if(arrayL[i]<=arrayR[j])
			arrayA[k]=arrayL[i++];
		else
			arrayA[k]=arrayR[j++];	
	}
}

下面演示了合并排序在对一个数组的处理过程:


上图中的合并排序过程的总的测试程序如下:

#include<iostream>
#include<ctime> 
using namespace std;

void Merge(int* arrayA,int p,int q,int r);
void MergeSort(int* arrayA,int p,int r);

void main()
{
	clock_t start,finish;
    double totaltime;
    start=clock();

	int arrayA[6]={5,2,4,6,1,3};
	int Length=sizeof(arrayA)/sizeof(int);
	MergeSort(arrayA,0,5);
	for(int i=0;i<Length;i++)
		cout<<arrayA[i];
	cout<<endl;

    finish=clock();
    totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
    cout<<"此两个程序的运行时间为"<<totaltime<<"秒!"<<endl;
	//上述由于数组太小,运行时间很短,可以循环

}

/***************************************
/              合并排序
/输入:数组arrayA、数组长度、p q r为数组下标
/输出:由小到大的数组
/时间复杂度:n
***************************************/

void Merge(int* arrayA,int p,int q,int r)
{
	int i=0;
	int j=0;
	int n1=q-p+1;//计算两个数组的长度
	int n2=r-q;//且这两个数组是已排列好的数组
	int arrayL[100]={0};//数组大小要大于n1
	int arrayR[100]={0};//数组大小要大于n2
	for(i=0;i<n1;i++)//对两个数组赋初值
		arrayL[i]=arrayA[p+i];
	    arrayL[i]=10000;//作为哨兵,判断是否到结尾
	for(i=0;i<n2;i++)   //也可以不用哨兵
		arrayR[i]=arrayA[q+i+1];
	    arrayR[i]=10000;

    i=0;j=0;
	for(int k=p;k<=r;k++)
	{
		if(arrayL[i]<=arrayR[j])
			arrayA[k]=arrayL[i++];
		else
			arrayA[k]=arrayR[j++];	
	}
}


/***************************************
/              
/输入:数组arrayA、p  r为数组下标,用于对数组p-r的元素排序
/输出:由小到大的数组
/时间复杂度:最坏情况下为nlgn
***************************************/
void MergeSort(int* arrayA,int p,int r)
{
	int q=0;
	if(p<r)
	{
		q=(p+r)/2;//将数组进行分解
		MergeSort(arrayA,p,q);
		MergeSort(arrayA,q+1,r);
		Merge(arrayA,p,q,r);
	}
}

注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为:

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
} 



原文:http://blog.csdn.net/tengweitw/article/details/9056485

作者:nineheadedbird



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
8643 0
[LeetCode] Merge Two Sorted Lists 合并两个排好序的链表
链接:https://leetcode.com/problems/merge-two-sorted-lists/#/description难度:Easy题目:21.
851 0
【算法导论】选择排序法
选择排序法         选择排序其实是冒泡法的一种改进,其基本思路也是:先确定最小元素,再找次最小元素,最后确定最大元素。         它与冒泡排序的最大区别在于:冒泡排序是只要碰见比它大的元素就交换,而选择排序是直接将元素放在最终的确定位置,从而避免了多次交换过程。
932 0
【算法导论】桶排序
桶排序 时间复杂度为:O(n) 基本思想:将要排列的序列分成n组,每组分别进行排序,然后在合并到一起,这里面有分而治之的思想。实例说明:大家学c语言肯定学过switch-case结构,最常见的题型就是对成绩进行分类,但是这里我们是对其进行排名。
892 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10471 0
算法笔记--归并排序
归并排序是一种使用分治策略的排序算法,适用于待排序列整体无序、部分有序的情况。 1. 算法思想           递归地将待排序列等分为两个子序列,直到子序列有序(狭义得讲就是只有一个元素),再将两个子序列合并为一个新的有序序列。
654 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
12293 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
159
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载