归并排序的子步骤合并两个有序数组，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-路归并排序（也叫归并排序）
归并排序代码示例：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/151057.html