JS 學資料結構與演算法 (排序篇)— 快速排序法 Quick Sort

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

快速排序法

  • 選定一個基準值 (Pivot)
  • 將比基準值 (Pivot) 小的數值移到基準值左邊,形成左子串列
  • 將比基準值 (Pivot) 大的數值移到基準值右邊,形成右子串列
  • 分別對左子串列右子串列作上述三個步驟
  • 直到左子串列或右子串列只剩一個數值或沒有數值
快速排序法示意圖
let testArray = [34,25,78,67,109,1,18,76,200];
function quickSort(arr) { // 如果 array 為空陣列或只有一個元素,直接返回,不需排序。 if (arr.length <=1 ) { return arr; } let pivot = arr[arr.length -1]; // 將陣列元素最後一項設為基準值 let left = []; // 用來儲存比基準值小的元素 let right = []; // 用來儲存比基準值大的元素 for(let i = 0; i < arr.length - 1; i++) {
// 設定 i < arr.length - 1 是因為陣列最後一項被我們設為 pivot 因此不需考慮
if (arr[i] < pivot) { left.push(arr[i]) } else { right.push(arr[i]) } }return [...quickSort(left), pivot, ...quickSort(right)]// 也可以寫成: return quickSort(left).concat(pivot, quickSort(right))}const sortedArray = quickSort(testArray);console.log(sortedArray); // [ 1, 18, 25, 34, 67, 76, 78, 109, 200 ]
return [...quickSort(left), pivot, ...quickSort(right)]

--

--

--

什麼都想學的雜食性軟體工程師 🇹🇼 (https://github.com/kylemocode) 合作與聯繫 📪 oldmo860617@gmail.com

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
莫力全 Kyle Mo

莫力全 Kyle Mo

什麼都想學的雜食性軟體工程師 🇹🇼 (https://github.com/kylemocode) 合作與聯繫 📪 oldmo860617@gmail.com

More from Medium

Ernst Lubitsch and his touch of brilliance

Freedom is the Problem: The Suicide Squad — Film Review

Colloquialisms of the Sahara

MISDIAGNOSIS AND SECOND CHANCES