標籤：

前端工程師演算法系列~快速排序

10-15
前端工程師演算法系列~快速排序

來自專欄現代計算機3 人贊了文章

快速排序

一、原理解析

快速排序使用分治法策略來把一個序列分為兩個子序列。

步驟為：

  1. 從數列中挑出一個元素，稱為「基準」，
  2. 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任何一邊）。在這個分區結束之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
  3. 遞歸地（recursively）把小於基準值元素的子數列和大於基準值元素的子數列排序。
  4. 遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個演算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

以下是 JavaScript 版本的的代碼實現：

function quickSort(arr) { if(arr.length <= 1) { return arr } let leftArr = [] let rightArr = [] for(let i = 1; i < arr.length; i++) { if(arr[i] >= arr[0]) { rightArr.push(arr[i]) } else { leftArr.push(arr[i]) } } return quickSort(leftArr).concat(arr[0]).concat(quickSort(rightArr))}var arr = [10, 34, 21, 47, 3, 28]quickSort(arr)console.log(arr)

上面quickSort 函數內每次執行新創建兩個數組，多次遞歸後會創建大量數組，在空間上存在"浪費"。我們可以在原數組上操作

function quickSort(arr) { function _quickSort(arr, start, end) { if(start >= end) return let key = arr[end] let left = start, right = end - 1 while(left < right) { while(arr[left] < key && left < right) left++ while(arr[right] >= key && left < right) right-- [arr[left], arr[right]] = [arr[right], arr[left]] } if(arr[left] >= arr[end]) { [arr[left], arr[end]] = [arr[end], arr[left]] } else { // 如 [2, 1, 3, 4] left++ } _quickSort(arr, start, left - 1) _quickSort(arr, left + 1, end) } _quickSort(arr, 0, arr.length - 1) return arr}

  • 對於一個數組，挑選最後一個值作為參考值(key)
  • 從數組的頭部開始掃描，如果值比參考值小，繼續往後掃描，直到掃描到的值(左值)比參考值大
  • 從數組的尾部(參考值的前一個)開始掃描，如果值比參考值大，繼續往前掃描，直到掃描到的值(右值)比參考值小
  • 此時交換掃描停止時的這兩個值
  • 繼續上面的邏輯，直到左值和右值相遇
  • 如果相遇時的值大於等於參考值，讓參考值和相遇值調換位置(一般情況)
  • 如果相遇時的值小於參考值，不調換，但 left 後移以為 (特殊情況，如 [2, 1, 3, 4, 5])

講過上面的處理後，就會把數組變成以原數組末尾數字為分割（左邊都比它小，右邊都比它大）的數組。然後分別對參考值左側和右側通過類似的邏輯繼續處理。

二、效率測試

下面我們測試排序性能

let arr = randomArr(10000, 100)console.time(quickSort)quickSort(arr)console.timeEnd(quickSort)function randomArr( arrLen = 100, maxValue = 1000 ) { let arr = [] for(let i = 0; i < arrLen; i++) { arr[i] = Math.floor((maxValue+1)*Math.random()) } return arr}function quickSort(arr) { function _quickSort(arr, start, end) { if(start >= end) return let key = arr[end] let left = start, right = end - 1 while(left < right) { while(arr[left] < key && left < right) left++ while(arr[right] >= key && left < right) right-- [arr[left], arr[right]] = [arr[right], arr[left]] } if(arr[left] >= arr[end]) { [arr[left], arr[end]] = [arr[end], arr[left]] } else { // 如 [2, 1, 3, 4] left++ } _quickSort(arr, start, left - 1) _quickSort(arr, left + 1, end) } _quickSort(arr, 0, arr.length - 1) return arr}

經瀏覽器測試，對於長度為10000的數組，排序約需要2.67ms(100次平均值)， 對於長度為100000的數組，排序約需要 94ms(100次樣本平均值)。

三、複雜度分析

時間複雜度為 O(nlogn)

四、參考

喜歡就點個贊，。如果或者發現文章中的錯誤，或者有更好的建議，歡迎大家評論，

這些技術如何學習，有沒有免費資料？

對前端的技術，架構技術感興趣的同學關注我的頭條號，並在後台私信發送關鍵字：「前端」即可獲取免費的架構師學習資料

知識體系已整理好，歡迎免費領取。還有面試視頻分享可以免費獲取。關注我，可以獲得沒有的架構經驗哦！！

推薦閱讀：

TAG:前端工程師 | 演算法 | 前端開發 |