## 前言 本文主要講述快速排序的一些基本概念和代碼的部分。 ## 概念理解 快排是比較常見的排序方法，其基本邏輯是分為以下的幾個階段。 > 1）在數據集之中，選擇一個元素作為"基準"（pivot）。 2）所有小于"基準"的元素，都移到"基準"的左邊；所有大于"基準"的元素，都移到"基準"的右邊。 3）對"基準"左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。 ## 基本的代碼邏輯 ~~~ let quickSort = (arr) => { let len = arr.length if(len <= 1) { return arr } let middleIndex = Math.floor(len/2) let middle = arr.splice(middleIndex,1) let left = [] let right = [] for(let i = 0 ; i < len-1 ; i++){ if(arr[i]-middle<=0){ left.push(arr[i]) } else { right.push(arr[i]) } } return quickSort(left).concat([middle],quickSort(right)) } ~~~ - [codepen快排的案例](https://codepen.io/robinson90/pen/QVjaMB) ## 復雜度 最壞情況：需要進行n‐1 次遞歸調用，其空間復雜度為 O（n） 最好情況：需要logn次遞歸調用，其空間復雜度為O（logn）  ## 穩定性 快速排序是一種不穩定排序算法 例如：現有序列為[1, 0, 1, 3]，“基準”數字選擇為第二個1 在第一輪比較之后，變成了[0, 1, 1, 3]，左序列為[0]，右序列為[1, 3]（右序列的1是此前的第一個1） 不難發現，原序列的兩個1的先后順序被破壞了，改變了先后順序，自然就是“不穩定”的排序算法了 ## 快排進階 ## 參考文檔 - [快速排序（阮一峰）](http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html) -