排序演化(三):快速

NO IMAGE

快速排序

我們在歸併排序那裡,使用了歸併,從而讓效率明顯降低到了排序演化(三):快速

裡面運用了分而治之的思想,在運用該思想時使用遞歸,讓我們的產生了樹的結構

在樹的結構裡,我們發現這種效率會很高。

靈感1

排序演化(三):快速

上體育課的時候,體育老師或者體育委員,喊集合的時候,就會用這個手勢,表示快速集合。

這裡有個小細節,一定有個同學快速站在老師對面,然後我們根據中間人的身高,就知道自己應該是在老師的左邊還是右邊了。

等確定是在左邊或者右邊後,我們才會去思考我左邊的人是誰右邊的人是誰,再進行準確的比較。

但是這有兩個前提

  1. 在快速集合的時候,這個中間人能立馬站到老師面前,那是因為以前在安排整理隊伍的時候,已經排好的,這個中間人是根據記憶就快速站在老師面前的。
  2. 待除了中間人的同學判斷完左右之時,後續的調整大家都是靠記憶的,比如誰誰在我左邊,誰誰在我右邊

靈感2

我們現在回顧一下歸併排序

排序演化(三):快速

在紅色框內,我們先把原數組不斷切割,切割至最小規模。

然後才在藍色框內,把數組合並起來。

如果要改進這個排序算法?你會怎麼思考呢?

我們能不能把藍色框和紅色框的行為合二為一呢?

即切割的時候夾另數組有序的作用,切割完成時,數組就有序了?

靈感1 + 靈感2

那我們能不能那把靈感1的快速集合在靈感2的二合一思想結合呢?

對於數組

let arr = [11, 3, 13, 4, 15, 6, 17]

排序演化(三):快速

如果我們知道準確的中間值是 11的話,我們把比11小的數分割成左塊,比11大的數分割成右塊

排序演化(三):快速

然後再把藍色和紅色塊同理使用中間值分割

排序演化(三):快速

整個數組就儼然有序了呀!

在上面的分割中,我們是假裝已知了準確的中間值是誰。

問題來了,如果我們不排序,我們怎麼可能知道數組的中間值是誰呢?

那我們可以退一步來思考,既然我們無法知道準確的中間值

我們隨便取一個數,然後根據這個數的大小把整個數組直接大於該數和小於該數的元素兩半分開,那這兩半很可能不是等大。

既然隨便取了,為了有點中間值的意思,我們就取位置上中間的數吧,比如下圖中的 4

排序演化(三):快速

然後我們把比 4 大的數 作為左邊(包括4本身)

把比 4 小的數 作為右邊(不包括4本身了)

排序演化(三):快速

然後重複上面的動作,對已經分出來的小塊再去類中間值分割

比如,此時左邊的只有 4 和 3 了,中間的值取4,那就把3 放在 4的右邊了,即兩者交換

那右邊的中間的值就取15,於是,[13,11,6]成為新的子左塊,[15,16]成為新的子右塊

排序演化(三):快速

再對[13, 11, 6]做分割,我們就會發現整個數組已經有序了

排序演化(三):快速

代碼實現

中間的值這個名字太長了,我們就稱為主元(pivot)

let arr = [11, 3, 13, 4, 15, 6, 17]
let pivot = arr[Math.floor((0 + arr.length) / 2)]
console.log(pivot); // 4

排序演化(三):快速

現在問題來了,怎麼實現比 4 小的數在左邊,比 4 大的數在右邊呢?

這就有個特別重要的思想要介紹了: 垃圾分類思想:沒有垃圾,只有放錯位置的資源。

瞎說的

在pivot左邊的,是要比他小的

在pivot右邊的,是要比他大的

那如果在左邊遇到大於pivot的,我們就去右邊找個比pivot小的數,兩者一交換,就o啦!

既然要兩邊找,我們就需要使用兩個變量來緩存元素,這裡緩存的就是下標。

// 從左邊開始
let i = 0
// 從右邊開始
let j = arr.length - 1

排序演化(三):快速

那很顯然,x往右找,即i++

y往左找,即y-—

我們先讓x找,x找到比4的數時,就停止,然後讓y找個比4大的數,最後兩者交換

停止的條件就是 x 小於等於 y吧

那交換過後,x和y還是要繼續找的,所以就x++,y- -,不然指著原來的數,有啥意思。

但是生活總是骨感的,如果其中一邊找不到呢?

比如arr = [1, 3, 13, 4, 15, 6, 17]

先 i 不斷加加找到比 4 大的數,即arr[2] : 13

那讓 j 不斷減減找到比4小的數,只能是arr[1]:3

此時這個arr[1]已經是在左邊了呀!那還有必要交換嗎?

當然不需要呀!

所以我們交換前要做個if (i <= j)判斷,這要兩邊找到了才交換

為什麼是<=,留在後面說

那我們要做什麼嗎?

不用,你沒發現 i 所指的位置arr[3],即13

[1,3][13,4,15,6,17]

剛好是大小兩半的分割點嗎?就是我們一開始想要的結果呀!

function partition(arr, left, right) {
const pivot = arr[Math.floor((left + right) / 2)]
let i = left
let j = right
while (i <= j) {
while (arr[i] < pivot) i++
while (pivot < arr[j]) j--
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
i++
j--
}
}
}
let arr = [11, 3, 13, 4, 15, 6, 17]
partition(arr, 0, arr.length - 1)
console.log(arr);
// [ 4, 3, 13, 11, 15, 6, 17 ]

那我們再回顧下,我們這個函數的作用是啥?

是讓數組分成大小兩部分,那此時我返回 i

調用者就能很好的把數組分割成大小兩部分

function quickSort(arr) {
return quick(arr, 0, arr.length - 1)
}
function quick(arr, left, right) {
if (arr.length > 1) {
let index = partition(arr, left, right)
if (left < index - 1) quick(arr, left, index - 1)
if (index < right) quick(arr, index, right)
}
return arr
}
function partition(arr, left, right) {
let pivot = arr[Math.floor((left + right) / 2)]
let i = left
let j = right
while (i <= j) {
while (arr[i] < pivot) i++
while (pivot < arr[j]) j--
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
i++
j--
}
}
return i
}

那快速排序就寫好了。

function quick(arr, left, right) {
if (arr.length > 1) {
let index = partition(arr, left, right)
if (left < index - 1) quick(arr, left, index - 1)
if (index < right) quick(arr, index, right)
}
return arr
}

既然let index = partition(arr, left, right)返回的index是數組大小兩部分的分割點(大部分的第一個元素)

quick(arr, left, index - 1)就表示再對這個小部分數組再分割

quick(arr, index, right)就表示再對這個大部分數組再分割

同理再分割前記得判斷,這個數組至少有兩個,不然left和index-1都是指向同一個元素,完全沒必要分割也分割不出來呀。

當數組只有一個的時候,就無法再分割了。

此時的數組也就有序了,為什麼有序了呢?再回去看上面的圖片。

這裡講下為什麼判斷條件一定要是<=

當數組不斷分割後,數組已經有序時

arr = [2,4,6,11,33,55,77]

此時low === 3,height === 4

function partition(arr, low, height) {
const pivot = arr[Math.floor((low + height) / 2)] // pivot === arr[3] === 11
let i = low // i === 3
let j = height // j === 4
while (i < j) {
while (arr[i] < pivot) i++ // 跳過
while (pivot < arr[j]) j-- // arr[j] === arr[3] === 11
if (i < j) { // i === 3, j === 3, 跳過
[arr[i], arr[j]] = [arr[j], arr[i]]
i++
j--
}
}
return i // i === 3
}

然後進入

function quick(arr, low, height) {
// low === 3, height === 4
if (arr.length > 1) {
const index = partition(arr, low, height) // index = 3
if (low < index - 1) quick(arr, low, index - 1) // 3 < 2
if (index < height) quick(arr, index, height) // 3 < 4 進入 quick(arr, index, height)
}
return arr
}

重點來了此時進入

quick(arr, index, height) // index === 3, height === 4

我們就會開始無限循環這個步驟了.

為什麼呢?

問題出在

我們在對3~4分組後,我們應該返回的是4

這樣在後續的分組中才會分成

3 ~ (4-1)4 ~ 4

這樣的話,就說明此分組已經只有一個元素了,不會繼續再分了

如果返回的是3

分組的情況就是

3~(3-1)3~4

會誤以為還能繼續分,就不斷循環分3~4

效率(匆忙)

別的先不說,對比歸併排序有個顯著的提升就是:不需要額外的空間了!

時間複雜度是 排序演化(三):快速,且性能通常比其他複雜度排序演化(三):快速的排序算法要好。

效率以後再認真寫,現在沒時間。

然後 ,前面歸併排序講過 快速排序是不穩定的

相關文章

092反轉鏈表II(JS)

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

206反轉鏈表(JS)

Promise.all和Promise.race源碼實現