合并数组并排序（合并数组并排序怎么弄）



归并排序的子步骤合并两个有序数组，merge /mɜːdʒ/ 合并

（一）“归并”含义是将两个或两个以上的有序表组合成一个新的有序表。无论是顺序存储结构还是链表存储结构，都可在O(m+n)的时间量级上实现。

合并两个有序数组过程：

例如 a = [1, 2] ， b = [0, 3, 4] 两个有序数组和一个空数组 res = [ ]，设置两个指针，i 指向 a 数组第一个元素，j 指向 b 数组第一个元素。首先比较这两个元素 1 < 0，将0添加到 res 数组[0]；然后让 j 指针递增指向 3 元素, 此时比较 i 和 j 指向元素 对比1 < 3,将 1 添加到 res 数组[0, 1] ； 让 i 指针递增指向2 元素, 此时比较 i 和 j 指向元素 对比2 < 3，将2添加到res数组[0, 1, 2]。这个时候 i = len(a)已经把 a 数组元素添加完，还剩 b 数组中3 和 4元素，直接把剩下b数组元素添加到 res [0, 1, 2 ,3 , 4]，这样就实现了合并两个有序数组为一个有序数组。

1.合并两个有序数组，要求 a[n]，b[m]，时间复杂度O[n+m]之内

代码一：

代码二：

（二）在实现合并两个有序数组的基础上实现归并排序

归并排序(Merging Sort)又是一类不同的排序方法。利用归并的思想容易实现排序。假设初始序列含有 n 个记录，则可看成是 n 个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，..... ,如此重复，直至得到一个长度为 n 的有序序列为止。这种排序方法称为 2-路归并排序（也叫归并排序）

归并排序代码示例：

版权声明：

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

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