归并排序(递归和非递归)

归并排序主要讲二路归并排序

二路归并排序的基本思想:

     设数组a中存放了n个数据元素,初始时把他们看成是n个长度为1的有序子数组,然后从第一个子数组开始,把相邻的子数组进行两两合并,的到n/2的整数上界个长度为2的新的有序子数组(当n为奇数时最后一个新的有序子数组的长度为1);对这些新的有序子数组在两两归并;如此重复,直到得到一个长度为n的有序数组为止。

归并排序的过程图:

归并排序的完整代码(非递归):

#include<iostream>
#include<malloc.h>
using namespace std;
 void meger(int *arr,int len,int gap)
{
	int *buff=(int*)malloc(sizeof(int)*len);//设置一个临时的buff
	if(buff==NULL)
	{
		exit(0);
	}
	int i=0;
	int low1=0;
	int high1=low1+gap-1;
	int low2=high1+1;
	int high2=(low2+gap-1)  < len ? (low2+gap-1) : (len-1);//当第二段的数据小于len时,就用第二段的数据

	while(low2<len) //第二段有数据时候,第二段有数据才能进行归并
	{
		while(low1<=high1 && low2<= high2)
		{
			if(arr[low1]<=arr[low2])
			{
				buff[i++]=arr[low1++];
			}
			else if(arr[low1]>arr[low2])
			{
				buff[i++]=arr[low2++];
			}
		}
		while(low1<=high1)//第一段中有剩余,一定不要忘记写等号
		{
			buff[i++]=arr[low1++];
		}
		while(low2<=high2)//第二段中有剩余,不要忘记写等号
		{
			buff[i++]=arr[low2++];
		}
		low1=high2+1;
		high1=low1+gap-1;
		low2=high1+1;
		high2=(low2+gap-1) <len ? (low2+gap-1) : (len-1)  ;
	}
	while(low1<len)//只有第一段,没有第二段
	{
	   buff[i++]=arr[low1++];
	}
	for(int j=0;j<len;++j)
	{
		arr[j]=buff[j];//把数据拷贝过来
	}
	free(buff);
}

void merger_sort(int *arr,int len)
{
	for(int gap=1;gap<len;gap*=2)//把带排序的数组进行排序
	{
		meger(arr,len,gap);
	}
}
int main()
{
	int arr[]={12,56,89,45,1,46};
	int len=sizeof(arr)/sizeof(arr[0]);
	merger_sort(arr,len);
	for(int i=0;i<len;i++)
	{
		cout<<arr[i]<<"  ";
	}
	cout<<endl;
}

归并排序的代码(递归):

#include<iostream>
#include<malloc.h>
using namespace std;
#define  maxsize   10

void megering(int *left,int left_size,int *right,int right_size)
{
	int i=0;
	int j=0;
	int k=0;
	int temp[maxsize];//用来存储排序的数据
	while(i<left_size && j<right_size)
	{
		if(left[i]<=right[j])//左边数据《 右边的数据
		{
			temp[k++]=left[i++];//就把左边的数据存储到temp数组中
		}
		else
		{
			temp[k++]=right[j++];//右边的数据小,就存储右边的数据
		}
	}
	while(i<left_size)//左边的数据有剩余,直接把左边的数据拷贝到temp数组中
	{
		temp[k++]=left[i++];
	}
	while(j<right_size)//右边的数据有剩余,就把右边的数据拷贝到temp数组中
	{
		temp[k++]=right[j++];
	}
	for(int m=0;m<(left_size+right_size);++m)
	{
		left[m]=temp[m];//最后的结果存在left数组中
	}
}
void meger_sort(int *arr,int len)
{
	if(len>1)//递归调用的出口
	{
		int *left=arr;//left指向数组的首地址
		int left_size=len/2;//len/2代表的是数组一半的数据,left_size代表的是左半部分的数据个数
		int *right=arr+len/2;//right指向的是右边部分的首元素
		int right_size=len-left_size;//右边部分元素的个数
		
		meger_sort(left,left_size);//划分左边,递归左半部分,即左边一直分,直达只有一个元素
		meger_sort(right,right_size);//划分右边,递归右半部分,即右边一直分,直到只有一个元素

		megering(left,left_size,right,right_size);//归并
	}
}
int main()
{
	int arr[]={1,8,4,50,4};
	int len=sizeof(arr)/sizeof(arr[0]);
	meger_sort(arr,len);
	for(int i=0;i<len;i++)
	{
		cout<<arr[i]<<"  ";
	}
	cout<<endl;
}

版权声明:本文为lingling_nice原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lingling_nice/article/details/80955007

智能推荐

[java][事务]tcc事务实战学习过程

学习项目:https://github.com/14251104246/spring-cloud-rest-tcc 下载源码,进入源码目录运行:mvn clean package Docker Compose运行 docker-compose -f infrastructure-compose.yml up -d docker-compose -f basic-ms-compose.yml up ...

[学习记录,]Mybatis入门

环境: Eclipse 2019 Tomcat 9.0 jdk1.8 开搞 首先创建工程 结构如下 导入Jar包 可在mybatis官网下载 http://www.mybatis.cn/82.html 配置文件mybatis-config.xml 事务管理有两种:JDBC和MANAGED JDBC: MANAGED 数据源类型:UNPOOLED、POOLED、JNDI 创建实体类文件User.ja...

运用for语句来判断数组中值得大小

总结: 1将if语句与数组联合起来判断输入中各组中的最大最小值; 2注意:定义的数组数量是躲多少就要输入多少组数据,少输入就无法输出;...

Bridging signals

Bridging signals Time Limit: 1000MSMemory Limit: 10000K Total Submissions: 10926Accepted: 5982 Description 'Oh no, they've done it again', cries the chief designer at the Waferland chip factory. Once ...

一天一大 leet

一天一大 leet 题目(难度:困难): 示例 抛砖引玉 官方答案 高手在民间 菜鸡的自白 20200606 题目(难度:困难): 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例 示例 抛砖引玉 要求算法的时间复杂度为 O(n),即限制了只能循环一次; 先对数组排序 循环数组记录后一个元素等于前一个元素+1或者等于前一个元素的数量 满足条件++,不然重...

猜你喜欢

Tensorflow实现的CNN文本分类

https://blog.csdn.net/somtian/article/details/69359498 原博文, github 在这篇文章中,我们将实现一个类似于Kim Yoon的卷积神经网络语句分类的模型。 本文提出的模型在一系列文本分类任务(如情感分析)中实现了良好的分类性能,并已成为新的文本分类架构的标准基准。 本文假设你已经熟悉了应用于NLP的卷积神经网络的基础知识。 如果没有,建议...

JDBC新手入门教程

开发工具:idea 数据库:mysql jar包:junit-4.10 mysql-connector-java-8.0.18 junit-4.10下载 mysql-connector-java-8.0.18下载 注意1:jdbc的驱动因为使用的是mysql-connector-java-8.0.18,所以为(“com.mysql.cj.jdbc.Driver”),而不是(...

Lua 排序 table.sort

    正如C#中有Array.Sort(),lua中也有自己的排序方法即table.sort(table,function)。     lua中的排序默认是从大到小的排序;     传入一个方法参数,可以使排序从小到大; 打印结果:  ...

SURF算法简述及Python标记SURF特征检测实践

目录 一、SURF算法 1.算法简介 2.SURF与SIFT的具体差异 二、Python代码实践 1.测试环境 2.测试代码 3.核心函数 4.测试结果 一、SURF算法 1.算法简介 SURF(Speeded-Up Robust Features)加速稳健特征,是一种稳健的局部特征点检测和描述算法。 SURF是对SIFT算法的改进,该算子在保持 SIFT 算子优良性能特点的基础上,同时解决了 S...

Selenium3自动化测试——19.读取数据文件

1. 实现目标 在测试与开发中,经常需要对文件进行各种读取操作。这里介绍针对txt、csv、xml、json文件的读取。 2. 读取TXT文件 2.1 user_info.txt文件 2.2 读取txt文件.py 2.3 实现结果 3. 读取csv文件 3.1 user_info.csv  这里要注意,csv文件本身打开是utf-8的,而不是乱码 3.2 读取csv文件.py 这里,针对...