合并排序（C语言实现)
递归算法是把一个问题分解成和自身相似的子问题，然后再调用自身把相应的子问题解决掉。这些算法用到了分治思想。其基本模式如下：
分解：把一个问题分解成与原问题相似的子问题
解决：递归的解各个子问题
合并：合并子问题的结果得到了原问题的解。
现在就用递归算法，采用上面的分治思想来解合并排序。
合并排序（非降序）
分解：把合并排序分解成与两个子问题
伪代码：
MERGE_SORT(A, begin, end)if begin < endthen mid<- int((begin + end)/2)MERGE_SORT(A, begin, mid)MERGE_SORT(A, mid+1, end)MERGE(A, begin, mid, end)
解决：递归的解各个子问题,每个子问题又继续递归调用自己，直到"begin<end"这一条件不满足时，即"begin==end"时，此时只有一个元素，显然是有序的，这样再进行下一步合并。
合并：合并的子问题的结果有个隐含问题，即各个子问题已经是排好序的了（从两个氮元素序列开始合并）。做法是比较两个子序列的第一个元素小的写入最终结果，再往下比较，如下图所示：
图中：待排序数组为2 4 6 1 3 5
把2 4 6和 1 3 5 分别存到一个数组中，比较两个数组的第一个元素大小小者存于大数组中，直到两小数组中元素都为32767.
这里32767 味无穷大，因为 c语言中 int类型是32位，表示范围是-32768-----32768。用无穷大作为靶子可以减少对两个小数组是否为空的判断，有了靶子，直接判断大数组元素个数次就排完了。
在整个过程中执行过程示如下图：
分解+执行时自上向下，合并时自下向上。
代码奉上：
#include <stdio.h>void MERGE(int *A, int b, int m, int e){ int l = m-b+1, r = e-m, i;int L[l+1], R[r+1];for(i=0; i< l; i++){L[i] = A[b+i];}for (i=0; i< r; i++){R[i] = A[m+i+1];}L[l] = 32767;R[r] = 32767;l = 0;r = 0;for(i=0; i< e-b+1; i++){if(L[l] < R[r]){A[b+i] = L[l];l ++;}else {A[b+i] = R[r];r ++;}} }void MERGE_SORT(int *A, int b, int e){if(b < e){int m = (b + e) / 2;MERGE_SORT(A, b, m);MERGE_SORT(A, m+1, e);MERGE(A, b, m, e);} }int main(){int A[500];int lens, i;printf("Please Enter the lenghth of array:");scanf("%d", &lens);printf("Please Enter the elements of the array:");for(i=0; i< lens; i++)scanf("%d", &A[i]);MERGE_SORT(A, 0, lens-1); printf("the result of the sort is:\n");for(i=0; i< lens; i++){printf("%d ", A[i]);}return 0;}
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/02/21/2919934.html，如需转载请自行联系原作者
相关文章：
工程实践也能拿KDD最佳论文？解读Embeddings at Airbnb
作者 | Mihajlo Grbovic，Airbnb 资深机器学习科学家译者 | Lang Yang，Airbnb 工程经理【导读】本文最早于 2018 年 5 月 13 日发表，主要介绍了机器学习的嵌入技术在 Airbnb 爱彼迎房源搜索排序和实时个性化推荐中的实践。Airbnb 爱彼迎的两位…
计算点、线、面等元素之间的交点、交线、封闭区域面积和闭合集(续1)
继续上一节的内容，本节主要讲解三维空间中射线、线段与平面及三维物体的交点及距离的计算，它们在碰撞检测和可见性剔除等应用中是必不可少的。首先给出3D空间下点乘和叉乘的定义与定理的推导，再谈如何应用到程序编码的工作中。 设三维空间中任…
android 抓取native层奔溃
使用android的breakpad工具 使用这个工具需要下载Breakpad的源码，然后进行编译，编译之后会生成两个工具 我们使用这两个工具来解析奔溃的位置。这里我们可以下载已经编译好的工具 下载地址是：链接：http://pan.baidu.com/s/1jIiU5c…
渗透各行各业，这家RPA外企宣布全面进军中国市场
11月15日，全球机器人流程自动化（RPA）领域平台UiPath首次在中国举办UiPath Together年度大会，来自自动化、人工智能和机器学习领域的行业专家，以及来自中国和世界的领先公司的客户与合作伙伴共同参与了此次活动。在此次…
java gettext_JAVA中getText()怎么从一个JTextArea中读出内容？
想先创建一个JTextArea，然后在里面输入内容(几个字母)，然后用getText读出里面的内容，可是好像只能是先在JTextArea里面写，然后getText才能读出，而不能先运行，在图形界面的JTex...想先创建一个JTextArea&…
想在SqlDbHelper.cs类中加的垃圾方法
虽然没改写SqlDbHelper.cs类的能力，但好不容易想出来的，放着留个纪念~~~~~/**//// <summary> /// 执行SQL语句，返回第一行，第一列（sea） /// </summary> /// <param na…
java全站_javaWeb_全站编码
目的 : 实现javaweb项目的全站编码问题需要解决的问题 : 在何时进行编码问题的解决, 在何处进行编码问题的解决, 才用什么方法进行解决设计思路 : 在Filter进行全站的编码转换, 对于GET请求 : 使用装饰者模式(是你有你一切拜托你), 修改Request.getParameter()方法, 在getparam…
在Linux系统中修改目录的权限如何恢复
在我工作中的某一天执行了chmod -R 777 /home后我十分后悔，这下不知道该怎么办？心里面很是着急。此时灵机一动问了一下谷哥，终于找到了方法解决此问题，不过前提是要自己做了文件权限备份工作，现在我就给大家讲解一下我…
.Net Framework 3.5 结构图
从打印社用A0或A1的纸打出来，大概10RMB，看起来超爽。 转载于:https://www.cnblogs.com/habin/archive/2008/03/15/1107196.html
关于CVPR 2019投稿的一些感想
作者 | 胡国圣，英国 anyvision 高级研究员，从事深度学习，人脸识别的研究。一年一度的 CVPR 是人工智能的机器视觉方向最重要的学术会议，每年吸引都会全球最顶尖的大学和公司的研究人员投稿，文章如果被录用，…
ORACLE 数据泵导入导出数据
一、摘要 在平常备库和数据库迁移的时候，当遇到大的数据库的时候在用exp的时候往往是需要好几个小时，耗费大量时间。oracle10g以后可以用expdp来导出数据库花费的时间要远小于exp花费的时间，而且文件也要小很多。 二、exp/imp与expdp/impdp区…
java备忘录模式应用场景_图解Java设计模式之备忘录模式
图解Java设计模式之备忘录模式游戏角色状态恢复问题游戏角色有攻击力和防御力，在大战Boss前保存自身的状态(攻击力和防御力)，当大战Boss后攻击力和防御力下降，从备忘录对象恢复到大战前的状态。传统方案解决游戏角色恢复传统的方式的问题分析…
一文掌握常用的机器学习模型（文末福利）
AI 科技大本营按：本文节选自微软亚洲研究院机器学习研究团队刘铁岩、陈薇、王太峰、高飞合著的《分布式机器学习：算法、理论与实践》一书。为了让大家更好地理解分布式机器学习，AI科技大本营联合华章科技特别邀请到了本书的作者之一——微软亚…
MYSQL替换语句
update dede_art set titlereplace(title, <IMG border0 srcImages/hot.gif>,);update 表名(比如我案例中的dede_art) set 要修改字段名 replace (要修改字段名,被替换的特定字符,替换成的字符) SELECT * FROM supe_spaceitems where subject like %狐狸天空% update …
phpstudy+phpstorm+debug
文:phpstudyphpstormdebug 一、配置前说明： 1、phpStudy集成了XDebug扩展，所以不用单独下载XDebug。 2、打开XDebug扩展：其它选项菜单 > PHP扩展 > Xdebug 二、配置步骤： 1、phpStudy当前版本： 2、修改php.ini…
java 卖票问题_Java之多线程窗口卖票问题(Thread)
/**** 例子：创建三个窗口卖票，总票数为100张.使用继承Thread类的方式** 存在线程的安全问题，待解决。**/class Window extends Thread{private static int ticket 100;Overridepublic void run() {while(true){if(ticket > 0){System.out…
雷军深情告白：在我心里，武汉大学是全球最好的大学
武汉大学将在 11 月 29 迎来 125 周年校庆，作为杰出校友，小米创始人雷军参加了昨天举行的第五届校友珞珈论坛。现场，雷军对武大深情表白：“马云在几个场合说过，杭州师范大学在他心里是全球最好的大学，没有之…
java中抽象接口_一篇文章让你彻底理解java中抽象类和接口
相信大家都有这种感觉：抽象类与接口这两者有太多相似的地方，又有太多不同的地方。往往这二者可以让初学者摸不着头脑，无论是在实际编程的时候，还是在面试的时候，抽象类与接口都显得格外重要！希望看完这篇博…
linux proc
/proc文件系统下的多种文件提供的系统信息不是针对某个特定进程的，而是能够在整个系统范围的上下文中使用。可以使用的文件随系统配置的变化而变化。 /proc/cmdline 这个文件给出了内核启动的命令行。 /proc/cpuinfo 这个文件提供了有关系统CPU的多种信息。 /proc/d…
专访英特尔AIPG全球研究负责人Casimir Wierzynski：物理学、隐私和大脑将根本性塑造AI
出品| AI 科技大本营 在 11 月 14 日至 15 日在北京召开的英特尔人工智能大会（AIDC）上，英特尔人工智能产品事业部（AIPG）全球研究负责人 Casimir Wierzynski 发表了主题为《人工智能研究——物理学、隐私和大脑》的演讲…
微软OOXML申请国际文档标准已获通过 中国投反对票
51CTO.com北京时间3月28日中午通过消息灵通人士获悉，微软新一代文档标准OOXML已经获得国际标准化组织（ISO）的通过。中国依然投反对票。 ISO共有104个成员，其中包括41个技术能力强、参与标准化活动多的“P成员”。若微软文档标准想…
java中的匿名类方法覆盖_Java技巧：用匿名类来实现简化程序调试
Java技巧：用匿名类来实现简化程序调试在Java中，匿名类(Anonymous inner classes)多用来处理事件(event handle)。但其实，它们对于debug也很有帮助。本文将介绍如何利用匿名类来简化你的debug。我们该如何调试那些非自己源码的方法调用呢&…
记录第一次在egret项目中使用Puremvc
这几天跟着另一个前端在做一个小游戏，使用的是egret引擎和puremvc框架，这对于我来说还是个比较大的突破吧，特此记录下。 因为在此项目中真是的用到了mvc及面向对象编程，值得学习 记录第一次在egret项目中使用Puremvc： …
使用CSS制作圆角效果
Web2.0中，圆角效果是很常见的，以前都是用图片来模仿，现在直接用css就能实现，例子代码如下 Html代码： <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> &…
知识图谱升温之势已现，不要错失下一个AI风口
近年来，随着大家对高级认知能力的积极探索，知识图谱因为表达能力强，扩展性好，并能兼顾人类认知与机器自动处理，引起了学术界、工业界以及政府部门的高度关注。 最先被大家熟知的应用领域应属搜索引擎，为了…
干货 | 谷歌BERT模型fine-tune终极实践教程
作者 | 奇点机智从11月初开始，Google Research就陆续开源了BERT的各个版本。Google此次开源的BERT是通过TensorFlow高级API—— tf.estimator进行封装(wrapper)的。因此对于不同数据集的适配，只需要修改代码中的processor部分，就能进行代码的…
java简介 ppt 精_《JAVA》5选择结构精篇课件.ppt
《JAVA》5选择结构精篇课件选 择 结 构 if 语句 if – else语句 Switch语句 块作用域语句又被称为复合语句，其格式为：用一对花括号将若干条语句括起来，目的是从语法上可以将多条语句解释成一条语句。 { int temp; temp a; a b; …
UPDATE STATISTICS 有何妙用?
txlicenhe 马可 一直没有关注它，今天刚学到的一招，还没彻底弄清楚。 情况是这样，有一个视图，用到了好几个表，其中一个表改了一些资料，在前台操作时总是超时过期（前台设置超时时间不长 60s&#…
js with用法
1）简要说明 with 语句可以方便地用来引用某个特定对象中已有的属性，但是不能用来给对象添加属性。要给对象创建新的属性，必须明确地引用该对象。 2）语法格式 with(object instance) { //代码块 } 有…
大数据时代，谁的眼神锁定你？
数据时代当前，欢迎来到楚门的世界。双十一余韵未歇，刚处理完一波售后及退件等“剁手后遗症”的各方人马也已经为再战双十二做好了准备。截至 12 日零点，天猫双十一成交额达 2135 亿元。与此同时，据国家邮政局监测数据显示…