分治法之合并排序(2021/1/23)_分治法合并程序-程序员宅基地

技术标签: 算法  c++  算法学习  合并排序  数据结构  

问题引入

在这里插入图片描述

代码实现

#include<iostream>
#include<cstdlib>
using namespace std;
struct Data{
    
	int flag;
};
void MergeFunction(struct Data*list,int low,int middle,int high){
    
	//申请辅助空间
	int size=high-low;
	struct Data*space=(struct Data*)malloc(sizeof(struct Data)*size);
	int i=low,j=middle+1;
	int now=0;
	while(i<=middle||j<=high){
    
		if(i<=middle&&j<=high){
    
			//比较i j flag
			if(list[i].flag<list[j].flag){
    
				space[now++]=list[i++];
			}else{
    
				space[now++]=list[j++];
			} 
		}else if(i<=middle){
    //i迭代全装入space 
			space[now++]=list[i++]; 
		}else{
    //j迭代装入space 
			space[now++]=list[j++];
		}
	}
	//将space内的内容装入原来列表内
	for(i=low;i<=high;i++){
    
		list[i]=space[i-low];
	} 
	free(space);
}
void MergeSort(struct Data*list,int low,int high){
    
	if(low>=high){
    //=说明只有一个元素不用排序 
		return;
	}
	int middle=(low+high)/2;
	//对middle左边排序
	MergeSort(list,low,middle);
	//对middle右边排序 
	MergeSort(list,middle+1,high);
	//合并
	MergeFunction(list,low,middle,high);
}
int main(int argc,char**argv){
    
	struct Data list[5]={
    {
    34},{
    5},{
    2},{
    7},{
    10}};
	MergeSort(list,0,4);
	//输出
	for(int i=0;i<5;i++){
    
		cout<<" "<<list[i].flag;
	} 
	cout<<endl;
	return 0;
}

程序输出

 2 5 7 10 34

--------------------------------
Process exited after 0.08149 seconds with return value 0
请按任意键继续. . .
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45812941/article/details/113029072

智能推荐

gt911多点触摸实验_gt911编程指南-程序员宅基地

文章浏览阅读4.5k次,点赞3次,收藏12次。文章目录一、设备树二、驱动程序三、测试四、编译进内核1. 拷贝文件2. 修改对应的 Makefile3. 编译运行4.测试一、设备树记得注释掉共用的引脚(有好几处)在pinctrl_tsc节点下添加: pinctrl_tsc: tscgrp { fsl,pins = < MX6UL_PAD_GPIO1_IO09__GPIO1_IO09 0x10B0 /* TSC_INT*/ MX6UL_PAD_SNVS_TAMPER9__GPIO5_IO09 0x10B0 /* TSC_gt911编程指南

Element-UI登录页面案例分享(Demo)_elementui登录页面-程序员宅基地

文章浏览阅读6.4k次,点赞5次,收藏28次。【辰兮要努力】:hello你好我是辰兮,很高兴你能来阅读,昵称是希望自己能不断精进,向着优秀程序员前行!博客来源于项目以及编程中遇到的问题总结,偶尔会有读书分享,我会陆续更新Java前端、后台、数据库、项目案例等相关知识点总结,感谢你的阅读和关注,希望我的博客能帮助到更多的人,分享获取新知,大家一起进步!吾等采石之人,应怀大教堂之心,愿你们奔赴在各自的热爱中…最近打算系统的整理一下一个vue + element-ui框架的简单应用。分模块整理一下demo,以及部分基础知识,分享给初学者,同时自._elementui登录页面

白平衡算法_白平衡色温增益曲线怎样算出来的-程序员宅基地

文章浏览阅读3.3k次,点赞3次,收藏10次。本文转载:http://blog.csdn.NET/wzwxiaozheng/article/details/384343911,白平衡算法---色温曲线本文大体讲解了白平衡的算法流程,适用于想了解和学习白平衡原理的筒子们.一般情况下要实现AWB算法需要专业的图像和算法基础,本文力图通过多图的方式,深入浅出,降低初学者理解上的门槛,让大家都理解到白平衡算法流程._白平衡色温增益曲线怎样算出来的

惠普m154a打印机硒鼓图解_教你一分钟完成硒鼓安装、加粉操作-程序员宅基地

文章浏览阅读3.6k次。硒鼓如何安装、加粉?作为耗材小白的你面对一支硬邦邦的硒鼓却一脸茫然?不要怕,硒鼓安装、加粉并不难,格之格“一分钟课堂”,教你如何正确对硒鼓进行安装和加粉!01 为什么用388系列硒鼓作为示范? 硒鼓主要分为鼓粉一体盒还有鼓粉分离盒,而市面上使用最广泛的惠普388系列、惠普2612系列以及三星的101系列、111系列都是鼓粉一体盒。而在其中,使用最为广泛的就是惠普的388系列。本期主要以惠普388..._惠普m154a加粉教程

iOS -- 播放本地音频文件 (Swift)_swift audioservicesplaysystemsound 本地文件-程序员宅基地

文章浏览阅读1.2k次。1.封装的方法,项目中如果多处使用,可以放在工具类中 static func play(name:String,type:String) { let audioPath = Bundle.main.path(forResource: name, ofType: type) if let filePath = audioPath { let url = URL(fileURLWithPath: filePath) var sou_swift audioservicesplaysystemsound 本地文件

DBUtils完成增删查改_dbutil实现增删改查-程序员宅基地

文章浏览阅读324次。DbUtils概述DbUtils是Apache组织提供的一个对JDBC进行简单封装的开源工具类库,使用它能够简化JDBC应用程序的开发,同时也不会影响程序的性能DbUtils常用API 创建QueryRunner对象的API public QueryRunner(DataSource ds) ,提供数据源(连接池)本程序代码传入DruidUtils连接池,可根据个人需求抽取其他连接池后调用其他连接池,DBUtils底层自动维护连接connection QueryRunner执.._dbutil实现增删改查

随便推点

移动端自适应适配布局的方法总结_移动端自适应布局-程序员宅基地

文章浏览阅读1.8k次。方法一:rem布局(个人最喜欢的方法)首先确定你的设计稿是基于iphone6还是iphone4/5:如果设计稿基于iphone6,横向分辨率为750,body的width为750 / 100 = 7.5rem如果设计稿基于iphone4/5,横向分辨率为640,body的width为640 / 100 = 6.4rem(1).对视口做如下设置:<meta name="viewport" content="initial-scale=1,maximum-scale=1, minimum_移动端自适应布局

第六章 前端开发——Vue框架-程序员宅基地

文章浏览阅读1.1k次。第六章 前端开发学习——Vue框架一、Vue介绍二、Vue实例三、Vue视图四、Vue组件五、Vue过度动画一、Vue介绍1.前端框架介绍A)前端框架有React FacebookAngular GoogleVue 全世界B)Angular、Vue、React的区别Vue与ReactRea..._是什么前端框架

wx.showToast显示新增成功后返回上一个界面_wx.showtoast 返回-程序员宅基地

文章浏览阅读920次。wx.showToast({ title: '新增成功', icon: 'success', duration: 1000, mask: true, success: function() { setTimeout(function() { //要延时执行的代码 wx_wx.showtoast 返回

Spring之设值注入和构造注入_spring设置注入和构造注入的区别-程序员宅基地

文章浏览阅读667次。设值注入 设置注入的本质是通过调用setter方法注入属性值。 构造注入 构造注入的本质是通过调用有参数构造函数注入属性值。 示例代码结构如下:其中beans.xml的代码如下:<?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.o..._spring设置注入和构造注入的区别

sqlalchemy学习笔记-程序员宅基地

文章浏览阅读683次。SQLAlchemy是python的一个数据库ORM工具,提供了强大的对象模型间的转换,可以满足绝大多数数据库操作的需求,并且支持多种数据库引擎(sqlite,mysql,postgres, mongodb等),在这里记录基本用法和学习笔记一、安装通过pip安装$ pip install SQLAlchemy二、使用首先是连接到..._with dbsession.engine.connect() as con

Request对象的所有的方法_把视频里request对象的代码-程序员宅基地

文章浏览阅读374次。setAttribute(String name,Object):设置名字为name的request的参数值getAttribute(String name):返回由name指定的属性值getAttributeNames():返回request对象所有属性的名字集合,结果是一个枚举的实例getCookies():返回客户端的所有Cookie对象,结果是一个Cookie数组getCharacterEncoding():返回请求中的字符编码方式getContentLength():返回请求的_把视频里request对象的代码