排序在我们的的工程应用中无处不见，也有着非常重要的作用，比如你随意点开一个搜索引擎，搜索的结构就是经过排序而来。各种电商网站的秒杀活动，用户点击秒杀后，服务器会根据用户的请求时间进行排序。在我们的用的文档表格中，也存在各种排序。
所以排序真的是无处不见，所以在我们面试中出现排序也不足为奇了。今天就为大家带来面试中经常出现的一种排序算法，合并排序进行深度解析。
合并排序本质上与二叉树的后序遍历非常类似的。
首先你还先回忆一下二叉树的后续遍历，后序遍历有个三个重要的特点：
// 递归function postOrder(root, array = []) { if (root === null) return null; postOrder(root.left, array); postOrder(root.right, array); array.push(root.val)}对于合并排序来说，其实也是非常类似：
简单利用伪代码表示就是：
function 后序遍历/合并排序： sub = 子结构（子树/子数组） full = 整合（sub）不管是后续遍历，还是合并排序的三个特点，这里可以总结为三个关键点：
对于二叉树而言，子树的划分是天然的，已经在数据结构里面约定好了，比如 Node.left、Node.right。
root.leftroot.right 可以直接通过树的子节点拿但是对于数组而言，在切分的时候，如果想到达最优的效率，那么将数组切为平均的两半效率应该是最高的。
const mid = begin + ((end - begin)>>1)数组a = [begin, mid) => 表示左子数组数组a = [mid, end) => 表示右子数组对于二叉树来说，获取子结构的信息就是或者左右子节点的信息。
postOrder(root.left)postOrder(root.right)对于合并排序来说，那么就分别需要对左子数组和右子数组进行排序。对子数组的排序，只需要递归就可以了。
merge(a, begin, mid)merge(a, mid, end)接下来，我们需要将从子结构里面拿到的信息进行加工。不同的需求会导致加工的方式也不太一样。
对于二叉树来说，非常简单，就是将节点值添加到结果中。
array.push(root.val)对于合并排序而言，我们需要将两个有序的子数组，合并成一个大的有序的数组。
let i = begin;let j = mid;let to = begin;// 将两个数组合并，判断条件是，只有左右子数组中还有元素while(i < mid || j < end) { // 读取左数组的元素： // - 左数组还存在元素并且左数组的开头元素小于右数组的开头元素 // - 右数组没有元素 if ((i < mid && a[i] < a[j]) || j >=end) { // t 为临时数组 t[to++] = a[i++]; } else { // 读取右数组的元素 t[to++] = a[j++]; }}最后，不管是二叉树还是合并排序都要考虑一下边界：
二叉树的边界就是节点不能为空。
if (root === null) return null;合并排序的边界就是：
if (b > e || b + 1 >= e) { return }对于二叉树来说，代码相对比较简单。
function postOrder(root, array = []) { // 边界处理 if (root === null) return null; // 第一步：划分子结构，二叉树在结构上已经划分了子结构 root.left、root.right 可以直接通过树的子节点拿 // 第二步：获取子结构信息（递归的方式） postOrder(root.left, array); postOrder(root.right, array); // 第三步：整合子结构信息 array.push(root.val)}对于二叉树来说，如何切分左右子数组？如何进行合并，合并时注意循环的条件，以及稳定排序的写法？都是在写算法时需要注意的。
function merge(a, t, b, e) { // 边界处理 if (b > e || b + 1 >= e) { return } /*********************核心代码****************************/ // 第一步：划分子结构 const mid = b + ((e-b)>>1); // 第二步：获取子结构信息（递归的方式） merge(a, t, b, mid); // 左边子结构 merge(a, t, mid, e); // 右边子结构 // 第三步：整合子结构信息 let i = b; let j = mid; let to = b; // 注意：下面是一个很重要的模板❤❤❤❤❤❤❤❤❤❤❤❤ // 将两个数组合并，判断条件是，只有左右子数组中还有元素 while(i < mid || j < e) { // 读取左数组的元素： // - 左数组还存在元素并且左数组的开头元素小于右数组的开头元素 // - 右数组没有元素 if ((i < mid && a[i] < a[j]) || j >=e) { t[to++] = a[i++]; } else { // 读取右数组的元素 t[to++] = a[j++]; } } /*********************核心代码****************************/ // 将合并的结果拷贝到源数组中 for (let i = b; i < e; i++) { a[i] = t[i]; }}function mergeSort(nums) { if (nums === null || nums.length === 0) { return; } merge(nums, [], 0, nums.length) return nums;}接着我们利用刚才将的例子来看几个例子。
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
这道题目就可以套用我们上面提到的模板。
第一步：划分子结构，对于链表来说划分子结构，也就是找到链表的中间节点。链表找中间节点也就是利用我上一篇文章中讲到的“快慢指针”。
let fast = head, slaw = head;// 第一步：划分子结构，快慢指针，一个节点走一步，另外一个节点走两步，一快一慢// 这里 tail 相当于上面数组中的 end，对于链表来说，end 也就是 nullwhile(fast !== tail) { slaw = slaw.next; fast = fast.next; if (fast && fast !== tail) { fast = fast.next; }}const mid = slaw;第二步：获取子结构信息（递归的方式）。
// 第二步：获取子结构信息const list1 = sort(head, mid);const list2 = sort(mid, tail)第三步：整合信息，有了两个子结构信息，也就需要将两个子结构信息合成一个，对于链表来说就是合并两个有序链表。这里合并的过程中，还可以用到到我上一篇文章说到的“链表第一板斧，假头”。
// 第三步：整合，合并两个有序链表var merge = function(head1, head2) { const dummy = new ListNode(); let tail = dummy; let list1 = head1; let list2 = head2; while(list1 && list2) { if (list1.val < list2.val) { tail.next = list1; tail = list1; list1 = list1.next; } else { tail.next = list2; tail = list2; list2 = list2.next; } } if (list1) { tail.next = list1; } if (list2) { tail.next = list2; } return dummy.next;}最后少不了临界条件的判断。
if (head === null) { return head; } if (head.next === tail) { head.next = null; return head; }完整的代码如下：
var merge = function(head1, head2) { const dummy = new ListNode(); let tail = dummy; let list1 = head1; let list2 = head2; while(list1 && list2) { if (list1.val < list2.val) { tail.next = list1; tail = list1; list1 = list1.next; } else { tail.next = list2; tail = list2; list2 = list2.next; } } if (list1) { tail.next = list1; } if (list2) { tail.next = list2; } return dummy.next;}function sort(head, tail) { if (head === null) { return head; } if (head.next === tail) { head.next = null; return head; } let fast = head, slaw = head; // 第一步：划分子结构，快慢指针，一个节点走一步，另外一个节点走两步，一快一慢 // 这里 tail 相当于上面数组中的 end，对于链表来说，end 也就是 null while(fast !== tail) { slaw = slaw.next; fast = fast.next; if (fast && fast !== tail) { fast = fast.next; } } const mid = slaw; // 第二步：获取子结构信息 const list1 = sort(head, mid); const list2 = sort(mid, tail) // 第三步：整合，合并两个有序链表 return merge(list1, list2);}var sortList = function(head) { if (head === null || head.next === null) { return head; } return sort(head, null)};给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
这是一道来自百度的面试题。解法有很多，我们重点介绍基于合并模板的解法。
如果单纯的不考虑复杂度，通过合并排序，我们已经能够将两个有序的数组合并成一个有序的数组了，再取这个有序数组的中位数。
var findMedianSortedArrays = function(nums1, nums2) { function merge(a, t, b, e) { // 边界处理 if (b > e || b + 1 >= e) { return } /*********************核心代码****************************/ // 第一步：划分子结构 const mid = b + ((e-b)>>1); // 第二步：获取子结构信息（递归的方式） merge(a, t, b, mid); // 左边子结构 merge(a, t, mid, e); // 右边子结构 // 第三步：整合子结构信息 let i = b; let j = mid; let to = b; // 注意：下面是一个很重要的模板❤❤❤❤❤❤❤❤❤❤❤❤ // 将两个数组合并，判断条件是，只有左右子数组中还有元素 while(i < mid || j < e) { // 读取左数组的元素： // - 左数组还存在元素并且左数组的开头元素小于右数组的开头元素 // - 右数组没有元素 if ((i < mid && a[i] < a[j]) || j >=e) { t[to++] = a[i++]; } else { // 读取右数组的元素 t[to++] = a[j++]; } } /*********************核心代码****************************/ // 将合并的结果拷贝到源数组中 for (let i = b; i < e; i++) { a[i] = t[i]; } } const nums = [].concat(nums1, nums2); merge(nums, [], 0, nums.length); const mid = nums.length>>1; if (nums.length % 2 === 0) { return (nums[mid-1] + nums[mid]) / 2; } return nums[mid];};但是这样操作的话，时间复杂度就变成 O(N)，并且空间复杂度也是 O(N)。
如果在面试现场，面试官一定会问你，有没有更好的办法？所以我们应该有效地利用两个数组的有序性解决这道题。下面我会从简单的情况开始分析。
假设我们有一个一维有序数组，如果我们要拿第 9 小的数。（注：第 1 小就是最小的数。）只需要将前面 8 个数扔掉，然后排在前面的数就是第 9 小的数。
但是现在我们有多个有序数据，怎么办了？但是非常确认的是，我们如果想拿到第 9 小的数，一定需要丢 8 个数。
那么接下来，思考一下在两个数组 A，B 中如何扔掉这 8 个数？
图片
图片
所以总结一下，当我们需要丢弃 K 个元素的时候。k 是偶数的时候，我们只需要比较 A[k/2-1] 和 B[k/2-1] 的大小，谁小就扔掉对应的 [0...k/2-1] 这一段；k 是奇数的时候，我们只需要比较 A[k/2] 和 B[k/2] 的大小，谁小就扔掉对应的 [0...k/2] 这一段。不过由于整数在程序中的整除特性，我们可以将奇数和偶数的情况统一起来。需要扔掉 k 个数的时候，p = (k-1)/ 2，你只需要比较 A[p] 和 B[p] 的大小即可。如果 A[p] >= B[p]，那么就可以把 B[0....p] 这段都扔掉。
var findMedianSortedArrays = function(A, B) { let len = A.length + B.length; let alen = A.length, blen = B.length; let i = 0, j = 0; // 如果两个数组的总长度为0 //那么不用再找了，肯定是没有中位数的，这里直接返回一个0 if (len == 0) { return 0; } // 总长度为偶数的情况： // 如果有4个数，那么当扔掉1个数之后 // 接下来需要合并的两个数排[2,3]就是中位数 // 总长度为奇数的情况： // 比如如果有5个数，那么当合并掉2个数之后 // 接下来的那个排[3]位的就是中位数。 // 所以这里k表示：要扔掉的数的个数 // 第一步：划分子结构 let k = (len - 1) >> 1; // 第二步：找到子结构信息 while (k > 0) { // 我们需要比较A[p]与B[p] // 只不过当数组的起始位置是i和j的时候。 // 比较的元素就变成 A[i+p], B[j+p] let p = (k - 1) >> 1; // 这时直接比较A[i + p]和B[j+p]来决定谁可以被扔掉掉 // 注意这里扔掉的时候，只需要前移p + 1即可。 if (j + p >= blen || (i + p < alen && A[i + p] < B[j + p])) { i += p + 1; } else { j += p + 1; } k -= p + 1; } // 第三步：整合信息 // 把排在前面的数取出来 let front = (j >= blen || (i < alen && A[i] < B[j])) ? A[i++] : B[j++]; // 如果总长度为奇数，那么这个时候，front就是我们要找的中位数 if ((len & 1) == 1) { return front; } // 此时总的数目为偶数，那么需要再取一个数，求平均值。 let back = (j >= blen || (i < alen && A[i] < B[j])) ? A[i] : B[j]; return (front + back) / 2.0;};一共要合并的长度可以认为是 N/2，然后每次取一半进行合并。因此，合并次数为 O(lgN)，空间复杂度为 O(1)。
通过合并排序，可以将两个有序的数组合并成一个有序的数组了。合并是一个非常经典的模板代码，你一定要理解并且背下来，很多地方都会用。比如合并有序链表，合并数组。一个小小的合并模板可就以解决这么多问题，多积累模版可以帮助我们在面试中快速答题。
本文链接：http://www.28at.com/showinfo-26-12359-0.html有了这个代码模板，合并排序手到擒来
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
