c++合并数组（c++合并排序算法）



将两个有序的子数组合并为一个整体有序的数组跟幼稚园里小朋友排队的道理差不多。假设小一班和小二班的小朋友已经按照身高由低到高排好队了，你是幼儿园老师，需要将小一班和小二班的队列合并为按身高由低到高的单一队列，那么，你很容易得到下述算法：比较排头位的两位小朋友的身高，将其中较矮的小朋友“拉”到新的队列中去；重复上述过程直至两个队列的小朋友都被拉完为止。如果其中一个队列的小朋友提前被拉完，那么另一个队列的剩余小朋友依次拉入新队列即可。

本文引用自作者编写的下述图书; 本文允许以个人学习、教学等目的引用、讲授或转载，但需要注明原作者"海洋饼干叔叔"；本文不允许以纸质及电子出版为目的进行抄摘或改编。

1.《Python编程基础及应用》，陈波，刘慧君，高等教育出版社。免费授课视频

2.《Python编程基础及应用实验教程》, 陈波，熊心志，张全和，刘慧君，赵恒军， 高等教育出版社

3. 《简明C及C++语言教程》，陈波，待出版书稿。免费授课视频

通常而论，问题的求解难度和计算量通常随问题规模的增加而增大，随问题规模的减小而减小，且当问题的规模充分小时，问题易于求解。比如，10个数的排序问题比5个数的排序问题要复杂，而1个数的排序问题则易于求解，因为只包含1个元素的数组天然有序。这给我们提供了一种称之为分治法（device and conquer）的算法设计思路。

分治法的解题思路可以简单概括如下：

将分治法应用于排序问题，即为归并排序算法。归并排序（merge sort）的计算复杂性较冒泡排序要低一个数量级，其解题思路可概要如下：

图7-4展示了数组[8,4,2,9,5,3,1,7]的归并排序过程。首先是“分”，由于数组含有8个元素难以直接排序，将其分成两个子数组，分别是[8,4,2,9]和[5,3,1,7]。这些这些子数组仍然过大，递归拆分成8个仅包含1个元素的子数组，分别是[8]、[4]、[2]、[9]、[5]、[3]、[1]、[7]。由于1个元素的数组天然有序，这8个子数组都可视为有序数组。

接下来是“治”，将有序的子数组两两合并，[8]、[4]合并为[4,8]，[2]、[9]合并为[2,9]，[4,8]和[2,9]又合并为[2,4,8,9]，… [2,4,8,9]和[1,3,5,7]最终合并为原问题的解[1,2,3,4,5,7,8,9]。容易看出，在归并排序里，真正的排序工作是在子数组合并的过程中完成的。

归并排序的实现请见下述程序。

🚩第24行：如果下标low小于high，说明当前子问题至少有两个以上的元素，过于复杂，应进行分治。否则，当前子问题仅包含1个元素，天然有序，什么都不用做。

🚩第25 ~ 27行：将子问题分解成规模差不多大的两个子问题a[low,mid]和a[mid+1,high]，然后分别递归调用mergeSort()函数进行求解。在第26行、第27行的mergeSort()函数执行后，a[low,mid]和a[mid+1,high]分别递增有序，对应着两个子问题的解。再次说明，在C++中，整数除以整数的商为整数，小数部分会被舍弃。

🚩第28行：执行merge()函数将两个有序子数组a[low,mid]和a[mid+1,high]合并至a[low,high]。

接下来讨论merge()函数的工作原理。将两个有序的子数组合并为一个整体有序的数组跟幼稚园里小朋友排队的道理差不多。假设小一班和小二班的小朋友已经按照身高由低到高排好队了，你是幼儿园老师，需要将小一班和小二班的队列合并为按身高由低到高的单一队列，那么，你很容易得到下述算法：比较排头位的两位小朋友的身高，将其中较矮的小朋友“拉”到新的队列中去；重复上述过程直至两个队列的小朋友都被拉完为止。如果其中一个队列的小朋友提前被拉完，那么另一个队列的剩余小朋友依次拉入新队列即可。

🚩第6行：动态分配一个临时的数组空间t，用于暂存有序的结果数组。从下标low至下标high,共有high–low+1个元素。

🚩第20行：释放临时数组t。

🚩第7行：整数i赋值为左子数组的首元素下标，整数j赋值为右子数组的首元素下标，整数k则为临时结果数组t的当前操作下标。

图7-5表示子数组a[0,3]和a[4,7]合并过程中的一个中间状态。下标i指向4，说明左子数组中的2已经“拉”到了临时结果数组t；下标j指向5，说明右子数组中的1和3已经“拉”到了临时结果数组t；下标k值为3，说明t[0,2]中已包含了三个有序元素，接下来，程序将比较i所指向的4和j所指向的5，其中的较小者将被复制到t[k]。如果左子数组的元素4被复制，那么i加1，如果右子数组的元素5被复制，则j加1，每复制一个元素，k加1。

🚩第8 ~ 13行：循环比较下标i和下标j所指向的两个子数组的当前待处理元素，将其中较小值复制到t[k]。该循环一直持续到其中一个子数组“耗尽”为止。当i>mid时，说明左子数组耗尽，当j>high时，说明右子数组耗尽。

🚩第14 ~ 17行：前述循环结束后，左子数组或者右子数组可能还有剩余元素，依次复制到t。

🚩第18 ~ 19行：将临时结果数组t的内容复制到a[low,high]。读者需要注意，该for循环的初始化语句被一个逗号操作符分开，i的初始值为low，k的初始值为0；同样地，更新表达式也被逗号操作符分开，更新时，i和k都递增1。在整个循环过程中，i的取值范围为[low,high]，k的取值范围为[0,high-low+1)，其中，high-low+1是结果数组所包含的元素个数。读者如果对该for循环的初始化语句以及测试、更新表达式的含义感到困惑，建议回顾本书4.3节。

上述工作完成后，a[low,high]即为合并后的有序数组。

为了帮助更多的年轻朋友们学好编程，作者在B站上开了两门免费的网课，一门零基础讲Python，一门零基础C和C++一起学，拿走不谢！ 

简洁的C及C++

Python编程基础及应用

如果你觉得纸质书看起来更顺手，目前Python有两本，C和C++在出版过程中。

《Python编程基础及应用》https://item.jd.com/12962124.html   

《Python编程基础及应用实验教程》https://item.jd.com/13218563.html  

普通读者如果期望学习好编程（C、C++或者Python），欢迎加入频道：， 与众多志同道合的读者一起努力。

方法：在手机频道（需要安装较新的版本）中搜索下述关键词，找到对应频道，然后选择加入。频道号：w395n39434。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/17644.html