排序演化(二):歸併

NO IMAGE

歸併排序

靈感

記得在軍訓的時候,隊伍都是四排的

排序演化(二):歸併

每排都是有序的,我們這裡就默認左低右高。

訓練四排,當我們轉移目的地的時候,為了避免霸佔道路,我們就會變成一列縱隊

排序演化(二):歸併

我們當時的教官是怎麼快速讓四排變成一列的呢?

  1. 教官先走到我們的左邊
  2. 喊 向左轉,此時我們就變成了四列縱隊朝著教官了
  3. 教官比較一下四列隊伍的前面第一個人(共四人),比較四人的身高
  4. 挑出最矮的,站在一個新的地方排成一列縱隊
  5. 不斷重複比較四列隊伍的前面第一個人(共四人)的身高,挑出然後往新的隊伍添加

默認原本每排嚴格身高遞增,現實總教官總是目測的,沒那麼精確

分分鐘,四排就變成一列了。

看來這種方式的排序效果很棒呀!我們怎麼運用到數組排序中呢?

分割

我們思考下前面方法的前提

  • 兩隊以上的有序隊伍

這個前提突然就讓我們想到插入排序,我們把第一個元素當成有序隊列了。那此時較之前者的,這裡多了一個兩隊以上,那好辦呀!我們可以把整個隊列裡的人,每個人獨立為一體,視為一個有序隊列。完美!

那用代碼怎麼實現上面把一列隊伍最後切割成一個一個人的呢?

對半切,獲得對半後的結果,再對這個結果對半切,直到該結果為一個人。

再對分割後的結果對半切時,這個結果是有左右兩半的,所以對結果對半切,要對左右分別對切

let arr = [1, 2, 3, 4]
// 找到中間線,從0到中間線為左,從中間線到尾為右
const middle = arr.length / 2
const left = arr.slice(0, middle)
const right = arr.slice(middle, arr.length)
console.log('left:', left); //left: [ 1, 2 ]
console.log('right:', right); //right: [ 3, 4 ]

為了達到有序的效果,我們要不斷切,一直切到每個結果只有一個元素為止

function mergeSort(arr) {
// 切到隊列只有一個元素就不繼續切
if (arr.length > 1) {
// 找到中間線,然後對著中間線一刀切下去
const middle = Math.floor(arr.length / 2)
// 對半結果的左邊
const left = mergeSort(arr.slice(0, middle))
// 對半結果的右邊
const right = mergeSort(middle, arr.length)
}
// 此時每個隊列只有一人了 停止對半切
return
}

這裡使用了遞歸,看不懂的話,我也沒辦法了

合併

前提我們已經完成了。

現在我們要的是模擬教官的合併了。

上面軍訓的例子,教官是四排歸併成一列,我們簡單點,使用兩排歸併成一列

教官每次比較的都是兩列總的第一位同學,在編程裡我們要有下標來表示了,我們這裡需要用到兩個變量來表示

let left = [1, 4]
let right = [2, 3]
let i = 0
let j = 0
// 左隊第一位
console.log(left[i]); // 1
// 右隊第一位
console.log(right[j]); // 2

為什麼要使用兩個變量呢?因為當我們比較兩者後,會讓矮的那個人,走到另一個地方新成一隊,然後不斷往那隊伍裡添加,那如果走的是左隊第一位1arr[0,那現在的左隊第一位就為4,代碼表示起來就是arr[1]

let left = [1, 4]
let right = [2, 3]
let i = 0
let j = 0
const ret = []
// 左隊第一位
console.log(left[i]); // 1
// 右隊第一位
console.log(right[j]); // 2
// 比較
if (left[i] < right[j]) {
ret.push(left[i])
i++
} else {
ret.push(right[j])
j++
}
// 新隊伍
console.log(ret); // [ 1 ]
// 此時,左隊第一位
console.log(left[i]); // 4
// 此時,右隊第一位
console.log(right[j]); // 2

上面看懂的話,我們就把比較的那段代碼寫優雅點

ret.push(left[i] < right[j] ? left[i++] : right[j++])

i++在後面,表示先使用left[i],此時的i還沒加一,使用完後再把 i 的值加一,等於

ret.push(left[i])
i++

這個比較後插入的動作,什麼時候停止呀?

當其中一個隊伍沒人的時候,我們就不用比較了!這不是廢話嗎?

代碼表示起來就是,i 或 j 一旦無法表示數組裡的數時就停止,即隊伍沒人的意思

while (i < left.length && j < right.length)

當其中一個隊伍沒人的時候,另一個隊伍剩很多人怎麼辦呢?

直接走到新隊伍後面呀!

這四人絕對比新隊伍裡的任何一個人都高!而且這四人還是有序的。

如果想不明白的話,你思考下

當左隊還剩一個人的時候

此時右隊有四個人

左隊第一位和右隊第一位比,

左隊第一位矮,遂走到新隊伍後面(即,新隊伍中最高者)

右隊是有序遞增的,第一位已經比新隊伍中最高者高了(剛剛比過了呀)

那整個右隊當然是比新隊伍都高的。

那直接走到新隊伍後面就可以了呀!

這用代碼怎麼表示呢?

我們可以使用 concat

let ret = [1, 2, 3]
let right = [4, 5, 6]
console.log(ret.concat(right));
//[ 1, 2, 3, 4, 5, 6 ]

然後我們再思考一個點

如果左隊為空了,那麼右隊一定還有人

右隊為空了,那麼左隊一定還有人

為什麼呢?

當左右隊都只有一個人的時候

經過比較,就矮的那個就會離開

那此時,高的那個還在原隊伍中呀!

再綜合前面說的剩餘多人的情況時,直接添加到新隊伍後面

使用 slice來表示剩餘的人

let arr = [1, 2, 3, 4]
let j = 2
console.log(arr[j]); // 3
console.log(arr.slice(j)); //[ 3, 4 ]

結合前面說的就有下面這段代碼

ret.concat(i < left.length ? left.slice(i) : right.slice(j))

最後就有

let left = [1, 3, 5]
let right = [2, 4, 6, 8, 10]
function merge(left, right) {
let i = 0
let j = 0
const ret = []
// 表示一旦其中一個隊伍沒人 就停止
while (i < left.length && j < right.length) {
ret.push(left[i] < right[j] ? left[i++] : right[j++])
}
return ret.concat(i < left.length ? left.slice(i) : right.slice(j))
}
console.log(merge(left, right));
// [ 1, 2, 3, 4, 5, 6, 8, 10 ]

遞歸

現在我們分割和合並都完成了

分割

function mergeSort(arr) {
if (arr.length > 1) {
const middle = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, middle))
const right = mergeSort(arr.slice(middle, arr.length))
}
return
}

合併

function merge(left, right) {
let i = 0
let j = 0
const ret = []
while (i < left.length && j < right.length) {
ret.push(left[i] < right[j] ? left[i++] : right[j++])
}
return ret.concat(i < left.length ? left.slice(i) : right.slice(j))
}

兩者要怎麼結合呢?

我們只要在分割代碼中添加合併函數就可以了

function mergeSort(arr) {
if (arr.length > 1) {
const middle = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, middle))
const right = mergeSort(arr.slice(middle, arr.length))
+		arr = merge(left,right)    
}
return
}

一個歸併排序就出來啦

function mergeSort(arr) {
if (arr.length > 1) {
const middle = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, middle))
const right = mergeSort(arr.slice(middle, arr.length))
arr = merge(left, right)
}
return arr
}
function merge(left, right) {
let i = 0
let j = 0
const ret = []
while (i < left.length && j < right.length) {
ret.push(left[i] < right[j] ? left[i++] : right[j++])
}
return ret.concat(i < left.length ? left.slice(i) : right.slice(j))
}
let arr = [8, 7, 6, 5, 4, 3, 2, 1]
console.log(mergeSort(arr));
// [ 1, 2, 3, 4, 5, 6, 7, 8 ]

排序演化(二):歸併

我們添加的

    const left = mergeSort(arr.slice(0, middle))
const right = mergeSort(arr.slice(middle, arr.length))
+		arr = merge(left,right)    

是在兩個遞歸的後面,所以只有遞歸終結的時候,方才執行,此時left和right都表示一個數,把只有一個數的left和right合併成一組後,作為arr返回,而這個arr成了另一個函數裡的left,另一邊的right也是如此。

再不懂就自己看圖吧。

效率

空間效率

如果要算空間效率的話,我們上面的歸併排序寫法就有點奢侈和難以說明了.

主要是上面的寫法能很清楚的明白歸併的思想,上面能明白,此時再來看採用原地歸併這種寫法,就比較好懂了。

function mergeSort(arr) {
const arrTemp = []
sort(arr, arrTemp, 0, arr.length - 1)
return arr
}
function sort(arr, arrTemp, low, hight) {
if (hight <= low) return
// 取中間值,這麼寫是避免溢出 類似 (low+hight)/2
let middle = low + Math.floor((hight - low) / 2)
sort(arr, arrTemp, low, middle)
sort(arr, arrTemp, middle + 1, hight)
merge(arr, arrTemp, low, middle, hight)
}
// 將有序的arr[low...midddle]和arr[middle+1...hight]歸併
function merge(arr, arrTemp, low, midlle, hight) {
let i = low
let j = midlle + 1
// 將arr[low...hight]複製到arrTemp[low...hihgt]
// 因為arr[low...hight]是要存儲兩隊歸併後的有序結果
for (let k = low; k <= hight; k++) {
arrTemp[k] = arr[k]
}
for (let k = low; k <= hight; k++) {
if (i > midlle) arr[k] = arrTemp[j++]
else if (j > hight) arr[k] = arrTemp[i++]
else if (arrTemp[j] < arrTemp[i]) arr[k] = arrTemp[j++]
else arr[k] = arrTemp[i++]
}
}
let arr = [11, 2, 33, 4, 55, 6]
console.log(mergeSort(arr));
// [ 2, 4, 6, 11, 33, 55 ]

這裡我就點一下第22行的四種判斷表示的意思,能看懂就看懂了,看不懂的,到時自己去翻《算法》這本書吧

  1. 左半邊用盡(取右半邊的元素)
  2. 右半邊用盡(取左半邊的元素)
  3. 右半邊的當前元素小於左半邊的當前元素(取右半邊的元素)
  4. 右半邊的當前元素大於等於左半邊的當前元素(取左半邊的元素)

那上面空間上,我們就要創建了一個和arr等長的數組arrTemp 作為中間站。

那就很容易看出,歸併排序有個負作用,即需要額外的空間且與數組長度成正比,約一約,就是排序演化(二):歸併

時間效率

歸併排序在最壞情況下的比較次數和任意基於比較的排序算法所需的最少比較次數都是排序演化(二):歸併,這裡指是普通的歸併,其實歸併很有很多細節可以優化

略略的寫,沒太多時間深入。

穩定性

當相等的元素是無法分辨的,比如像是整數,穩定性並不是一個問題。然而,假設以下的數對將要以他們的第一個數字來排序。

(4,1)(3,1)(3,7)(5,6)

在這個狀況下,有可能產生兩種不同的結果,一個是讓相等鍵值的紀錄維持相對的次序,而另外一個則沒有:

(3,1)(3,7)(4,1)(5,6)(維持次序)
(3,7)(3,1)(4,1)(5,6)(次序被改變)

不穩定排序算法可能會在相等的鍵值中改變紀錄的相對次序,但是穩定排序算法從來不會如此。不穩定排序算法可以被特別地實現為穩定。作這件事情的一個方式是人工擴展鍵值的比較,如此在其他方面相同鍵值的兩個對象間之比較,(比如上面的比較中加入第二個標準:第二個鍵值的大小)就會被決定使用在原先數據次序中的條目,當作一個同分決賽。然而,要記住這種次序通常牽涉到額外的空間負擔。

歸併排序是穩定的,後面要講的 快速排序是不穩定的

相關文章

024兩兩交換鏈表中的節點(JS)

206反轉鏈表(JS)

Promise.all和Promise.race源碼實現

排序演化(三):快速