fbpx

大家好我是老莫,也可以叫我 Kyle

為什麼要寫這個主題?

之前在尋找實習職缺的過程中,遇到幾次當面或者電話面試考資料結構與演算法等技術題,測驗結束才發現自己沒有透徹了解這些概念,有些概念懂了卻不知道怎麼用程式語言實作出來,想當然面試結果並不理想。因此我決定設定這樣的主題,並以自己最擅長的語言 JavaScript 將資料結構或演算法實作出來,除了能夠了解背後的概念外,也有能力可以透過程式語言實作出來,並利用這些概念去解決真實狀況遇到的技術問題。

主題涵蓋的範圍?

這次 “JS 學資料結構與演算法” 系列預計會包含以下範圍:

  • 排序 (sort)
  • 搜尋 (sesrch)
  • 動態程式規劃 (dynamic programming)
  • Hash Table 雜湊表
  • Linked List 鏈結串列
  • Stack 堆疊
  • Queue 佇列
  • Tree 樹
  • Graph 圖形
  • Recursion 遞迴

其中各類別可能又會往下細分子類別依次介紹(如排序下細分各種排序法),我想這會是一個漫長的主題,但相信踏實地走完這趟旅程一定會讓基礎更加扎實,也能幫助像我一樣對這些觀念一知半解的讀者能有更透徹的理解,如果對這個主題有興趣的朋友們記得追蹤我囉!

*此後內容皆假設讀者了解基本演算法定義與時間複雜度概念


快速排序法

演算法定義:

快速排序法採用 Devide and Conquer 的概念,將一個大問題拆分成數個較小的子問題,再將子問題的結果整合成原問題的答案。

作法:

  • 選定一個基準值 (Pivot)
  • 將比基準值 (Pivot) 小的數值移到基準值左邊,形成左子串列
  • 將比基準值 (Pivot) 大的數值移到基準值右邊,形成右子串列
  • 分別對左子串列右子串列作上述三個步驟
  • 直到左子串列或右子串列只剩一個數值或沒有數值

快速排序法的效率和基準值 (Pivot) 的選擇息息相關,每次選擇的基準值 (Pivot) 愈接近數列的平均值或中位數愈好。

 

快速排序法示意圖

時間複雜度

最佳 :

O(n log n),第一個基準值的位置剛好是中位數,將資料均分成二等份。

最差:

Ο(n^2),當資料的順序恰好為由大到小或由小到大時,此時有分割跟沒有分割並沒有區別,反而做了多餘的操作。

平均:

O(n log n)


程式範例

 
let testArray = [34,25,78,67,109,1,18,76,200];

完整程式碼 Link

以上解法比較可能會讓讀者產生疑惑的是

return [...quickSort(left), pivot, ...quickSort(right)]

這邊使用了遞迴方法與 ES6 Spread Operator 的語法,遞迴在後面的章節會 cover 到,對 ES6 語法不熟的讀者可以參考 這篇文章


結語

最後必須要強調的是,同一種演算法其實有無數種解題方式,上面的解法不過是其中一種,並且未必是最好的解法,雖然確實可以達到排序的目的,但是也許在效能或記憶體運用卻仍有可以改善的空間。因此如果你們發現上面解法可以改進的地方,歡迎討論,如果你對這個系列有興趣,也想跟我一起透過 JavaScript 強化自己對於資料結構與演算法的基礎,歡迎訂閱我,如果覺得這篇文章對你有幫助,也不要吝嗇幫我拍拍手吧!

下回預告: 合併排序法(Quick Sort)

JS 學資料結構與演算法JS 學資料結構與演算法全系列:

(1) 快速排序法 Quick Sort (本篇)

(2) 合併排序法 Merge Sort

(3) 氣泡排序法 Bubble Sort

(4) 選擇排序法 & 插入排序法

 

「好文轉自莫力全 Kyle MoJS 學資料結構與演算法 (排序篇)— 快速排序法 Quick Sort,如果你喜歡他的文章歡迎回到他的部落格看更多:)」

希望以上能幫助到你藉由JS 更了解資料結構與演算法。如果想要對JavaScript本身有更多的瞭解,Udemy這裡開課囉!老師從基礎手把手的帶你實作,教你主流寫法提升 JS 開發能力!

如果你的入門還在單打獨鬥,歡迎來到快樂學程式找到志同道合的夥伴,你的自學之路不孤單。