iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 22
4
Software Development

前端工程師用 javaScript 學演算法系列 第 22

排序 4: 快速排序 Quick Sort

沒想到排序就寫了四篇 XD,終於要介紹最後一個排序法了,這是最常用的排序法之一,效能也相當不錯。

Big O(n logn):Quick Sort 快速排序

Quick Sort 會先選一個基準數 (pivot),然後其他元素跟 pivot 輪流比較,小的放前大的放後。pivot 兩邊也會切割成更小的 Array 直到只剩一個值,最後再組裝。

觀察步驟

一樣的題目如下

// before sort
[8, 9, 2, 5, 1]
// after sort
[1, 2, 5, 8, 9]

https://ithelp.ithome.com.tw/upload/images/20190923/20106426wNqvqDOXas.jpg

  • 隨便選一個值當基準數 (pivot)
  • 最左邊會有一個 pointer (指標) L,最右邊位置也會有一個 pointer R
  • R 往左移動直到找到一個小於 pivot 停下來
  • L 往右移動直到找到一個大於 pivot 停下來
    https://ithelp.ithome.com.tw/upload/images/20190923/20106426drv0nJIg0F.jpg
  • 值交換位置,L 跟 R 繼續移動
    https://ithelp.ithome.com.tw/upload/images/20190923/20106426o7zaiJR61C.jpg
  • 若一直沒有停下來,那 L 跟 R 重疊時,重疊的值跟基準(pivot)交換,當回合結束。

切割

  • 以基準值出發分為左右兩塊 Array
  • 繼續重覆上述步驟一直到 Array 只剩一個

組裝

把排序好的 Array 組裝

實際操作

我知道上面說明很難懂,還是來看範例好了

// 第一輪
// 第一次交換
[8, 9, 2, 5, 1]  // Determine pivot, I choose 8
 -

[8, 9, 2, 5, 1] // start pointer at left and right
 -
 L           R

[8, 9, 2, 5, 1] // R 找到一個 < 8 的停下來,因為 1 < 8 所以第一步就停了
 -
 L           R

[8, 9, 2, 5, 1] // L 找到一個 > 8 的停下來,他往右移到 9 就停住
 -
    L        R

[8, 1, 2, 5, 9] // When L & R all stop, swich position
 -
    L        R

// 第二次交換

[8, 1, 2, 5, 9] // 5 < 8, so stop
 -
    L     R

[8, 1, 2, 5, 9] // L 碰到 R 了但都沒發現 > 8 的,但碰到代表第一輪結束,把 pivot 跟 5 交換
 -
          LR

[5, 1, 2, 8, 9] 
 -        -

第一輪結束我們其實已經以 8 為分界 分成左邊 Array [5, 1, 2] 跟 右邊 Array [9] ,再來只要針對這兩邊再繼續做一樣的事情就好

// 第二輪   
[5, 1, 2]  // Determine pivot
 -

[5, 1, 2]  // start pointer at left and right
 -
 L     R

[5, 1, 2]  // R < 5, so stop
 -
 L     R

[5, 1, 2]  // L 沒找到 > 5 的直到碰到 R
 -
       LR

[2, 1, 5]  // 碰到代表這回合結束,交換位置
 -     -
       
// 第三輪
[2, 1]  // Determine pivot
 -

[2, 1]  // start pointer at left and right
 -
 L  R

[2, 1]  // 1 < 2, so stop
 -
 L  R


[2, 1]  //  碰到
 -
    LR

[1, 2]  //  碰到所以交換



// 第四輪  [9] 就不用排了

https://ithelp.ithome.com.tw/upload/images/20190923/201064262Ch0ScwLRc.jpg

程式碼

let data = [8, 9, 2, 5, 1];

let quickSort = (arr, L, R) => {
    // 實作劃分過程
    const partition = (array, L, R) => {
        let pivot = L + 1;
        for (let i = L + 1; i <= R; i++) {
            if (array[i] < array[L]) {
                swap(array, i, pivot);
                pivot++;
            }
        }

        // 記得把 pivot 跟最後一個比它小的元素互換
        swap(array, L, pivot - 1);
        return pivot - 1;
    }
    const _quickSort = (array, L, R) => {
        if (L >= R) return array;

        // 在 partition 裡面調整數列,並且回傳 pivot 的 index
        const pivotIndex = partition(array, L, R);
        _quickSort(array, L, pivotIndex - 1);
        _quickSort(array, pivotIndex + 1, R);
        return array;
    };
    return _quickSort(arr, 0, arr.length - 1);
}

// array 裡面的值自己交換 array[index1] = array[index2]
function swap(arr, index1, index2) {
    // es6 Destructuring
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
}

console.log(quickSort(data, 0, data.length - 1))

另外看到邦友 Gary 的文章也有實作快速排序覺得超簡潔的好厲害(如下)

function quickSort(arr) {
  if (arr.length < 2) return arr
  const [p, ...ary] = arr
  const left = [], right = []

  ary.forEach(c => {
    if (c < p) left.push(c)
    else right.push(c)
  })

  return [...quickSort(left), p, ...quickSort(right)]
}

排序其實非常多種,也有難到我無法理解的 XD,但覺得至少我介紹這五種要知道 "概念" 在幹嘛,真正寫出程式我倒覺得其次。雖然可以訓練一下思考邏輯但畢竟現實中可以直接用 Array.prototype.sort ....(咦那我這四天在幹麻)

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

歡迎追蹤我的部落格,除了技術文也會分享一些在矽谷工作的甘苦。


上一篇
排序 3: 合併排序 Merge Sort
下一篇
簡易搜尋 Sequential Search & 二分搜尋 Binary Search
系列文
前端工程師用 javaScript 學演算法32
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

1
微中子
iT邦新手 4 級 ‧ 2019-09-23 21:40:46

看到你用 var 建議不要用,就是用 constlet
swap 裡面得 tmpValue 應該要用 const

你寫的是迴圈版,Gary 是遞迴版,其實沒有誰好誰壞啦。遞迴看起來比較簡潔,但容易堆滿 stack,並且其實遞迴的效能「有可能」會略輸迴圈版(因為程式執行時候,遞迴需要在記憶體片段中重複跳躍,function 通常會再另外一個片段,所以會再 main 和 function 之間反覆跳躍)

hannahpun iT邦新手 4 級 ‧ 2019-09-24 00:05:52 檢舉

謝謝你的建議 ~~

iT邦新手 2 級 ‧ 2022-03-18 17:40:36 檢舉

剛剛仔細看了一下,做個補充:
發現文章中,應該兩者都是用遞迴做法。

我在學習時確實漏掉了迴圈的方法,
當時還以為 quick sort 只能遞迴,
只要給太多 input 就會碰到 over stack 的問題。

這裡提供網路的迴圈做法供參考 (下面的)

我要留言

立即登入留言