有了這個(gè)代碼模板，合并排序手到擒來
排序在我們的的工程應(yīng)用中無處不見，也有著非常重要的作用，比如你隨意點(diǎn)開一個(gè)搜索引擎，搜索的結(jié)構(gòu)就是經(jīng)過排序而來。各種電商網(wǎng)站的秒殺活動(dòng)，用戶點(diǎn)擊秒殺后，服務(wù)器會(huì)根據(jù)用戶的請(qǐng)求時(shí)間進(jìn)行排序。在我們的用的文檔表格中，也存在各種排序。
所以排序真的是無處不見，所以在我們面試中出現(xiàn)排序也不足為奇了。今天就為大家?guī)砻嬖囍薪?jīng)常出現(xiàn)的一種排序算法，合并排序進(jìn)行深度解析。
合并排序本質(zhì)上是一個(gè)后續(xù)遍歷
合并排序本質(zhì)上與二叉樹的后序遍歷非常類似的。
首先你還先回憶一下二叉樹的后續(xù)遍歷，后序遍歷有個(gè)三個(gè)重要的特點(diǎn)：
- 拿到子樹的信息；
- 利用子樹的信息；
- 整合出整棵樹的信息。
// 遞歸
function postOrder(root, array = []) {
if (root === null) return null;
postOrder(root.left, array);
postOrder(root.right, array);
array.push(root.val)
}對(duì)于合并排序來說，其實(shí)也是非常類似：
- 拿到子數(shù)組的信息；
- 利用子數(shù)組的信息；
- 整合（排序）出整個(gè)數(shù)組的信息。
簡單利用偽代碼表示就是：
function 后序遍歷/合并排序：
sub = 子結(jié)構(gòu)（子樹/子數(shù)組）
full = 整合（sub）不管是后續(xù)遍歷，還是合并排序的三個(gè)特點(diǎn)，這里可以總結(jié)為三個(gè)關(guān)鍵點(diǎn)：
- 劃分子結(jié)構(gòu)
- 獲取子結(jié)構(gòu)的信息
- 利用子結(jié)構(gòu)的信息整合成一個(gè)樹/結(jié)果
1. 劃分子結(jié)構(gòu)
對(duì)于二叉樹而言，子樹的劃分是天然的，已經(jīng)在數(shù)據(jù)結(jié)構(gòu)里面約定好了，比如 Node.left、Node.right。
root.left
root.right
可以直接通過樹的子節(jié)點(diǎn)拿但是對(duì)于數(shù)組而言，在切分的時(shí)候，如果想到達(dá)最優(yōu)的效率，那么將數(shù)組切為平均的兩半效率應(yīng)該是最高的。
const mid = begin + ((end - begin)>>1)
數(shù)組a = [begin, mid) => 表示左子數(shù)組
數(shù)組a = [mid, end) => 表示右子數(shù)組2. 獲取子結(jié)構(gòu)的信息
對(duì)于二叉樹來說，獲取子結(jié)構(gòu)的信息就是或者左右子節(jié)點(diǎn)的信息。
postOrder(root.left)
postOrder(root.right)對(duì)于合并排序來說，那么就分別需要對(duì)左子數(shù)組和右子數(shù)組進(jìn)行排序。對(duì)子數(shù)組的排序，只需要遞歸就可以了。
merge(a, begin, mid)
merge(a, mid, end)3. 整合（排序）出整個(gè)數(shù)組/樹的信息。
接下來，我們需要將從子結(jié)構(gòu)里面拿到的信息進(jìn)行加工。不同的需求會(huì)導(dǎo)致加工的方式也不太一樣。
對(duì)于二叉樹來說，非常簡單，就是將節(jié)點(diǎn)值添加到結(jié)果中。
array.push(root.val)對(duì)于合并排序而言，我們需要將兩個(gè)有序的子數(shù)組，合并成一個(gè)大的有序的數(shù)組。
let i = begin;
let j = mid;
let to = begin;
// 將兩個(gè)數(shù)組合并，判斷條件是，只有左右子數(shù)組中還有元素
while(i < mid || j < end) {
// 讀取左數(shù)組的元素：
// - 左數(shù)組還存在元素并且左數(shù)組的開頭元素小于右數(shù)組的開頭元素
// - 右數(shù)組沒有元素
if ((i < mid && a[i] < a[j]) || j >=end) {
// t 為臨時(shí)數(shù)組
t[to++] = a[i++];
} else {
// 讀取右數(shù)組的元素
t[to++] = a[j++];
}
}最后，不管是二叉樹還是合并排序都要考慮一下邊界：
二叉樹的邊界就是節(jié)點(diǎn)不能為空。
if (root === null) return null;合并排序的邊界就是：
- 當(dāng) b >= e，說明這個(gè)區(qū)間是一個(gè)空區(qū)間，沒有必要再排序；
- 當(dāng) b + 1 === e，說明只有一個(gè)元素，也沒有必要排序。
if (b > e || b + 1 >= e) {
return
}小結(jié)
對(duì)于二叉樹來說，代碼相對(duì)比較簡單。
function postOrder(root, array = []) {
// 邊界處理
if (root === null) return null;
// 第一步：劃分子結(jié)構(gòu)，二叉樹在結(jié)構(gòu)上已經(jīng)劃分了子結(jié)構(gòu) root.left、root.right 可以直接通過樹的子節(jié)點(diǎn)拿
// 第二步：獲取子結(jié)構(gòu)信息（遞歸的方式）
postOrder(root.left, array);
postOrder(root.right, array);
// 第三步：整合子結(jié)構(gòu)信息
array.push(root.val)
}對(duì)于二叉樹來說，如何切分左右子數(shù)組？如何進(jìn)行合并，合并時(shí)注意循環(huán)的條件，以及穩(wěn)定排序的寫法？都是在寫算法時(shí)需要注意的。
function merge(a, t, b, e) {
// 邊界處理
if (b > e || b + 1 >= e) {
return
}
/*********************核心代碼****************************/
// 第一步：劃分子結(jié)構(gòu)
const mid = b + ((e-b)>>1);
// 第二步：獲取子結(jié)構(gòu)信息（遞歸的方式）
merge(a, t, b, mid); // 左邊子結(jié)構(gòu)
merge(a, t, mid, e); // 右邊子結(jié)構(gòu)
// 第三步：整合子結(jié)構(gòu)信息
let i = b;
let j = mid;
let to = b;
// 注意：下面是一個(gè)很重要的模板????????????
// 將兩個(gè)數(shù)組合并，判斷條件是，只有左右子數(shù)組中還有元素
while(i < mid || j < e) {
// 讀取左數(shù)組的元素：
// - 左數(shù)組還存在元素并且左數(shù)組的開頭元素小于右數(shù)組的開頭元素
// - 右數(shù)組沒有元素
if ((i < mid && a[i] < a[j]) || j >=e) {
t[to++] = a[i++];
} else {
// 讀取右數(shù)組的元素
t[to++] = a[j++];
}
}
/*********************核心代碼****************************/
// 將合并的結(jié)果拷貝到源數(shù)組中
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;
}接著我們利用剛才將的例子來看幾個(gè)例子。
例1：排序鏈表
給你鏈表的頭結(jié)點(diǎn) head ，請(qǐng)將其按 升序 排列并返回 排序后的鏈表 。
這道題目就可以套用我們上面提到的模板。
第一步：劃分子結(jié)構(gòu)，對(duì)于鏈表來說劃分子結(jié)構(gòu)，也就是找到鏈表的中間節(jié)點(diǎn)。鏈表找中間節(jié)點(diǎn)也就是利用我上一篇文章中講到的“快慢指針”。
let fast = head,
slaw = head;
// 第一步：劃分子結(jié)構(gòu)，快慢指針，一個(gè)節(jié)點(diǎn)走一步，另外一個(gè)節(jié)點(diǎn)走兩步，一快一慢
// 這里 tail 相當(dāng)于上面數(shù)組中的 end，對(duì)于鏈表來說，end 也就是 null
while(fast !== tail) {
slaw = slaw.next;
fast = fast.next;
if (fast && fast !== tail) {
fast = fast.next;
}
}
const mid = slaw;第二步：獲取子結(jié)構(gòu)信息（遞歸的方式）。
// 第二步：獲取子結(jié)構(gòu)信息
const list1 = sort(head, mid);
const list2 = sort(mid, tail)第三步：整合信息，有了兩個(gè)子結(jié)構(gòu)信息，也就需要將兩個(gè)子結(jié)構(gòu)信息合成一個(gè)，對(duì)于鏈表來說就是合并兩個(gè)有序鏈表。這里合并的過程中，還可以用到到我上一篇文章說到的“鏈表第一板斧，假頭”。
// 第三步：整合，合并兩個(gè)有序鏈表
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;
// 第一步：劃分子結(jié)構(gòu)，快慢指針，一個(gè)節(jié)點(diǎn)走一步，另外一個(gè)節(jié)點(diǎn)走兩步，一快一慢
// 這里 tail 相當(dāng)于上面數(shù)組中的 end，對(duì)于鏈表來說，end 也就是 null
while(fast !== tail) {
slaw = slaw.next;
fast = fast.next;
if (fast && fast !== tail) {
fast = fast.next;
}
}
const mid = slaw;
// 第二步：獲取子結(jié)構(gòu)信息
const list1 = sort(head, mid);
const list2 = sort(mid, tail)
// 第三步：整合，合并兩個(gè)有序鏈表
return merge(list1, list2);
}
var sortList = function(head) {
if (head === null || head.next === null) {
return head;
}
return sort(head, null)
};例2：尋找兩個(gè)正序數(shù)組的中位數(shù)
給定兩個(gè)大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的 中位數(shù) 。
算法的時(shí)間復(fù)雜度應(yīng)該為 O(log (m+n)) 。
這是一道來自百度的面試題。解法有很多，我們重點(diǎn)介紹基于合并模板的解法。
如果單純的不考慮復(fù)雜度，通過合并排序，我們已經(jīng)能夠?qū)蓚€(gè)有序的數(shù)組合并成一個(gè)有序的數(shù)組了，再取這個(gè)有序數(shù)組的中位數(shù)。
var findMedianSortedArrays = function(nums1, nums2) {
function merge(a, t, b, e) {
// 邊界處理
if (b > e || b + 1 >= e) {
return
}
/*********************核心代碼****************************/
// 第一步：劃分子結(jié)構(gòu)
const mid = b + ((e-b)>>1);
// 第二步：獲取子結(jié)構(gòu)信息（遞歸的方式）
merge(a, t, b, mid); // 左邊子結(jié)構(gòu)
merge(a, t, mid, e); // 右邊子結(jié)構(gòu)
// 第三步：整合子結(jié)構(gòu)信息
let i = b;
let j = mid;
let to = b;
// 注意：下面是一個(gè)很重要的模板????????????
// 將兩個(gè)數(shù)組合并，判斷條件是，只有左右子數(shù)組中還有元素
while(i < mid || j < e) {
// 讀取左數(shù)組的元素：
// - 左數(shù)組還存在元素并且左數(shù)組的開頭元素小于右數(shù)組的開頭元素
// - 右數(shù)組沒有元素
if ((i < mid && a[i] < a[j]) || j >=e) {
t[to++] = a[i++];
} else {
// 讀取右數(shù)組的元素
t[to++] = a[j++];
}
}
/*********************核心代碼****************************/
// 將合并的結(jié)果拷貝到源數(shù)組中
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];
};但是這樣操作的話，時(shí)間復(fù)雜度就變成 O(N)，并且空間復(fù)雜度也是 O(N)。
如果在面試現(xiàn)場，面試官一定會(huì)問你，有沒有更好的辦法？所以我們應(yīng)該有效地利用兩個(gè)數(shù)組的有序性解決這道題。下面我會(huì)從簡單的情況開始分析。
假設(shè)我們有一個(gè)一維有序數(shù)組，如果我們要拿第 9 小的數(shù)。（注：第 1 小就是最小的數(shù)。）只需要將前面 8 個(gè)數(shù)扔掉，然后排在前面的數(shù)就是第 9 小的數(shù)。
但是現(xiàn)在我們有多個(gè)有序數(shù)據(jù)，怎么辦了？但是非常確認(rèn)的是，我們?nèi)绻肽玫降?9 小的數(shù)，一定需要丟 8 個(gè)數(shù)。
那么接下來，思考一下在兩個(gè)數(shù)組 A，B 中如何扔掉這 8 個(gè)數(shù)？
- 要扔掉 4 個(gè)數(shù)，我們需要看一下兩個(gè)數(shù)組前 4 個(gè)元素（平均分配一下）；此時(shí)設(shè) A[3] = L，B[3] = W。假設(shè) L >= W，就需要證明：當(dāng) L >= W 的時(shí)候，[0, W] 都不可能是第 9 小的數(shù)，可以扔掉。
圖片
- 當(dāng)我們?nèi)拥?4 個(gè)數(shù)之后，兩個(gè)有序數(shù)組已經(jīng)變成如下圖所示的樣子，由于我們的目標(biāo)是扔掉 8 個(gè)數(shù)，扔掉 4 個(gè)數(shù)之后，還需要再扔 4 個(gè)數(shù)。此時(shí)我們只需要比較數(shù)組開頭的一個(gè)元素 A[0], B[M] 的大小，誰小就把誰扔掉。這里我們假設(shè) A[0] 比較小。
圖片
- 此時(shí)還剩下 3 個(gè)數(shù)需要扔掉，那么按照上面的方式在進(jìn)行丟棄就行。
所以總結(jié)一下，當(dāng)我們需要丟棄 K 個(gè)元素的時(shí)候。k 是偶數(shù)的時(shí)候，我們只需要比較 A[k/2-1] 和 B[k/2-1] 的大小，誰小就扔掉對(duì)應(yīng)的 [0...k/2-1] 這一段；k 是奇數(shù)的時(shí)候，我們只需要比較 A[k/2] 和 B[k/2] 的大小，誰小就扔掉對(duì)應(yīng)的 [0...k/2] 這一段。不過由于整數(shù)在程序中的整除特性，我們可以將奇數(shù)和偶數(shù)的情況統(tǒng)一起來。需要扔掉 k 個(gè)數(shù)的時(shí)候，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;
// 如果兩個(gè)數(shù)組的總長度為0
//那么不用再找了，肯定是沒有中位數(shù)的，這里直接返回一個(gè)0
if (len == 0) {
return 0;
}
// 總長度為偶數(shù)的情況：
// 如果有4個(gè)數(shù)，那么當(dāng)扔掉1個(gè)數(shù)之后
// 接下來需要合并的兩個(gè)數(shù)排[2,3]就是中位數(shù)
// 總長度為奇數(shù)的情況：
// 比如如果有5個(gè)數(shù)，那么當(dāng)合并掉2個(gè)數(shù)之后
// 接下來的那個(gè)排[3]位的就是中位數(shù)。
// 所以這里k表示：要扔掉的數(shù)的個(gè)數(shù)
// 第一步：劃分子結(jié)構(gòu)
let k = (len - 1) >> 1;
// 第二步：找到子結(jié)構(gòu)信息
while (k > 0) {
// 我們需要比較A[p]與B[p]
// 只不過當(dāng)數(shù)組的起始位置是i和j的時(shí)候。
// 比較的元素就變成 A[i+p], B[j+p]
let p = (k - 1) >> 1;
// 這時(shí)直接比較A[i + p]和B[j+p]來決定誰可以被扔掉掉
// 注意這里扔掉的時(shí)候，只需要前移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;
}
// 第三步：整合信息
// 把排在前面的數(shù)取出來
let front =
(j >= blen || (i < alen && A[i] < B[j])) ? A[i++] : B[j++];
// 如果總長度為奇數(shù)，那么這個(gè)時(shí)候，front就是我們要找的中位數(shù)
if ((len & 1) == 1) {
return front;
}
// 此時(shí)總的數(shù)目為偶數(shù)，那么需要再取一個(gè)數(shù)，求平均值。
let back =
(j >= blen || (i < alen && A[i] < B[j])) ? A[i] : B[j];
return (front + back) / 2.0;
};一共要合并的長度可以認(rèn)為是 N/2，然后每次取一半進(jìn)行合并。因此，合并次數(shù)為 O(lgN)，空間復(fù)雜度為 O(1)。
總結(jié)
通過合并排序，可以將兩個(gè)有序的數(shù)組合并成一個(gè)有序的數(shù)組了。合并是一個(gè)非常經(jīng)典的模板代碼，你一定要理解并且背下來，很多地方都會(huì)用。比如合并有序鏈表，合并數(shù)組。一個(gè)小小的合并模板可就以解決這么多問題，多積累模版可以幫助我們?cè)诿嬖囍锌焖俅痤}。
