【算法导论】合并排序法

简介:        分治法:将原问题划分为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



目录
相关文章
|
11月前
|
算法 搜索推荐
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
|
搜索推荐 算法
数据结构与算法——希尔、归并、快速排序
前面说完了三种较为简单的排序算法,分别是冒泡排序,选择排序和插入排序,它们的平均情况时间复杂度都是 O(n2),比较的高,适合小规模的数据排序,其中插入排序的效率稍高,所以更推荐使用插入排序。今天再来看看另外三种时间复杂度都是 O(nlogn) 的排序算法,分别是希尔排序、归并排序和快速排序。其中后两者的应用非常的广泛。
154 0
数据结构与算法——希尔、归并、快速排序
|
算法 Java Python
【算法导论】二分查找
1. 描述(查找算法):   输入:n个数的一个序列 A = (a1, a2, a3,.....an)和一个值v   输出:下表 i 使得 v=A[i] 或者 v 不在A中出现时,输出 NIL   二分查找的前提是A必须是有序序列, 以下全部假设是A是非降序序列 2.
1097 0
|
算法 搜索推荐 vr&ar
【算法导论】归并排序
1. 分治法:分治模型在每层递归的时都有三个步骤:   a.分解原问题为若干个子问题,这些子问题是原问题的规模较小的实例;   b. 解决这些子问题,递归地求解各子问题的规模足够小,则直接求解;   c. 合并这些子问题的解 成 原问题的解。
1533 0
|
存储 人工智能 算法
【算法导论】插入排序
没办法就是这么没原则,又开了个坑。每天看点书,不管什么书。 1. 需求:   输入:n个数的一个序列(a1, a2,  a3……an)   输出: 输出序列的一个排列(a1', a2', a3' ……an'),满足a1'
1157 0
|
算法 Python 机器学习/深度学习
|
存储 人工智能 算法
《算法导论(原书第3版)》一2.1 插入排序
本节书摘来自华章出版社《算法导论(原书第3版)》一 书中的第2章,第2.1节,作者:(美)Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1429 0