前端三十｜06. [JS] 請你在旁邊的白板寫個快速排序演算法。

今天是本系列進入 JavaScript 主題的第一天，那麼就先寫個 前陣子面試 時遇到的快速排序法吧！

本系列文已經重新編校彙整編輯成冊，並正式出版囉！

《前端三十：從 HTML 到瀏覽器渲染的前端開發者必備心法》好評販售中！

喜歡我文章內容的讀者們，歡迎您前往購買支持！

快速排序法

來寫個由小到大的版本吧，不囉嗦直接上 Code：

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

快速排序的基本概念就是先挑出一個 樞紐（pivot），接著將其他元素與樞紐輪流比較，在由小到大的情況中，比它小的往前放，比它大的往後放，放完的同時也就把樞紐的位置固定好了；接著再對「比他大的部分」及「比他小的部分」個別做一次一樣的事，周而復始，直到陣列為空或只有一個元素就直接回傳；這樣就完成排序囉～

不夠清楚嗎？這裡有 匈牙利傳統舞蹈版本的說明。

以上，就是今天的快速排序法，大家是不是學會了呢？我們明天見～

…
…
…

欸等等，快速排序是寫出來了啦，但你有沒有想過，為什麼要練習演算法？

演算法