iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 6
3
Modern Web

前端三十 - 成為更好的前端工程師系列 第 6

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

https://ithelp.ithome.com.tw/upload/images/20190922/20111380uYRlZy0uJ3.jpg

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

快速排序法

來寫個由小到大的版本吧,不囉嗦直接上 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),接著將其他元素與樞紐輪流比較,在由小到大的情況中,比它小的往前放,比它大的往後放,放完的同時也就把樞紐的位置固定好了;接著再對「比他大的部分」及「比他小的部分」個別做一次一樣的事,周而復始,直到陣列為空或只有一個元素就直接回傳;這樣就完成排序囉~

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

以上,就是今天的快速排序法,大家是不是學會了呢?我們明天見~

...
...
...

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

演算法

先思考一下,演算法的本質是什麼?其實就只是前人經驗與智慧的累積,是一些優秀的解決事情的方法。

大推這部 TedEd 的影片,淺顯易懂的說明了好的演算法效果有多驚人!

如果能理解各個演算法的思考過程,遇到合適的情境便能套用,甚至觸類旁通,思考出更好的解決方案;例如 Tim PetersMerge sortInsertion sort 的優點結合,利用原始資料中連續升序或降序的片段,進一步優化了排序,發明了 Timsort

換言之,學習演算法,就如同是在學習高手們的思考方式,讓你在面對問題時,能找出更「聰明」的解決方法。

面試

那為什麼許多公司行號的面試都喜歡考演算法呢?我認為有兩種可能:

  1. 把演算法當成一種門檻,認為熟知這些是這個職位的基本條件
  2. 藉由一個已知最佳解的問題,想鑑定求職者的邏輯是否正確、思路是否靈活清晰

第 1 種情況的公司其實還不少,可能一些熱門的職位求職者眾多,徵才方希望透過設定好的門檻,快速篩選出合適的人選,而演算法也會是門檻之一。

第 2 種情況,通常就是讓許多求職者感到害怕的現場筆試甚至白板題;但從徵才方的角度思考一下,其實也不用太過害怕,畢竟就只是想看你的思考邏輯,而不是要你一口氣默寫出最佳解,通常面試官也會給予適當的引導,只要順順的照著自己思考問題的模式,與團隊思考方式契合的人也自然會得到青睞。

雖然有人開玩笑說「面試造火箭,工作擰螺絲」,但演算法仍然是熱門的面試題目來源 XD

刻意練習

當然,有公司會考就有人會準備,訪間也有許多練習演算法的解題網站,最紅的莫過於 LeetCode,除了網羅全球各大公司的面試考古題外,在解題後能看到解題時間等數據指標,付費版的甚至有模擬面試,可以說所有軟體工程相關領域的求職者,或多或少都會在這打滾一陣子。

除了 LeetCode 外,我個人比較喜歡的是另一個解題網站:CodeWars,多了經驗值、等級、戰隊、排行榜等許多遊戲化的要素,並開放讓所有使用者自創題目,上面除了基本的演算法題型外,還有各種產業可能遇到的真實問題,甚至是 Code Golf 等等,讓你刷題不無聊。各種生活化的題型解起來也是別有一番樂趣。之前筆者有寫過另一篇 CodeWars 刷題心得分享,有興趣的讀者也可以參考一下。

刻意練習是很重要的事情,畢竟只是讀過看過,並不能讓人真正學會一件新事物;但我認為 目的只是通過面試的刻意練習演算法,是毫無意義的。透過大量的刷題,也許可以熟記這些演算法考古題的題型,但如果不能真正的認識、理解、掌握,進而內化成自己的功力,即使刷題刷好刷滿,最終也只是淪為背誦答案的考試機器。

結語

演算法與資料結構一直是軟體工程中重要的基礎學科,熟練掌握其中的知識也是發展職涯過程的必經之路;為了求職刷好刷滿,比不上為了讓自己更好更強的刻意練習。

這次真的是本篇文章的結尾了,我們大家明天見~

參考資料

筆者

Gary

半路出家網站工程師;半生熟的前端加上一點點的後端。
喜歡音樂,喜歡學習、分享,也喜歡當個遊戲宅。

相信一切安排都是最好的路。


上一篇
05. [CSS] 元素選取器是如何運作的?
下一篇
07. [JS] 瀏覽器 DOM 元素的事件代理是指什麼?
系列文
前端三十 - 成為更好的前端工程師31

2 則留言

2
huli
iT邦新手 5 級 ‧ 2019-09-22 20:12:10

這個快速排序法是我看過最簡單易懂的版本,而且有抓到精髓XD
不過缺點就如文章裡面講的,花費太多空間了
如果要改成原地交換版本的話其實要花不少時間而且複雜滿多XD

這邊附上一個之前寫過的原地交換版本(出自一起用 JavaScript 來複習經典排序法吧!

function quickSort = (arr) => {
  const swap = (array, i , j) => {
    [array[i], array[j]] = [array[j], array[i]];
  }
  const partition = (array, start, end) => {
    let splitIndex = start + 1;
    for (let i = start + 1; i <= end; i++) {
      if (array[i] < array[start]) {
        swap(array, i, splitIndex);
        splitIndex++;
      }
    }
  
    // 記得把 pivot 跟最後一個比它小的元素互換
    swap(array, start, splitIndex - 1);
    return splitIndex - 1;
  }
  const _quickSort = (array, start, end) => {
    if (start >= end) return array;
  
    // 在 partition 裡面調整數列,並且回傳 pivot 的 index
    const middle = partition(array, start, end);
    _quickSort(array, start, middle - 1);
    _quickSort(array, middle + 1, end);
    return array;
  };
  return _quickSort(arr, 0, arr.length - 1);
}
Gary iT邦新手 5 級 ‧ 2019-09-22 20:39:23 檢舉

謝謝大大幫補充~
/images/emoticon/emoticon41.gif

1
hannahpun
iT邦新手 5 級 ‧ 2019-09-22 23:48:13

你的版本真的好精簡,謝謝分享

看更多先前的回應...收起先前的回應...
hannahpun iT邦新手 5 級 ‧ 2019-09-22 23:55:17 檢舉

另外其實可以直接嵌入 youtube 影片,不知道作者用圖片在連結影片是有別的用意嗎?

Gary iT邦新手 5 級 ‧ 2019-09-23 00:07:33 檢舉

原來可以直接嵌入嗎!?
我用加入 Youtube 連結跑出來的也是圖片連結,我以為不行XD

hannahpun iT邦新手 5 級 ‧ 2019-09-23 10:43:57 檢舉

可以 好像只差在影片有 ![Yes]

Gary iT邦新手 5 級 ‧ 2019-09-23 11:16:25 檢舉

我以為 Yes 只是圖片描述,就改掉了XD

感謝!
/images/emoticon/emoticon41.gif

Yenting iT邦新手 5 級 ‧ 2019-09-23 23:18:55 檢舉

下次真的不現場示範刷題嗎 :D /images/emoticon/emoticon28.gif

我要留言

立即登入留言