前端工程師算法系列(5)-快速排序
快速排序
一、原理解析
快速排序使用分治法策略來把一個序列分為兩個子序列。
步驟為:
- 從數列中挑出一個元素,稱為“基準”,
- 重新排序數列,所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面(相同的數可以到任何一邊)。在這個分割槽結束之後,該基準就處於數列的中間位置。這個稱為分割槽(partition)操作。
- 遞迴地(recursively)把小於基準值元素的子數列和大於基準值元素的子數列排序。
- 遞迴到最底部時,數列的大小是零或一,也就是已經排序好了。這個演算法一定會結束,因為在每次的迭代(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)
四、參考
ofollow,noindex">維基百科-快速排序本文作者:若愚。喜歡就點個贊,後續才有動力繼續更新。如果或者發現文章中的錯誤,或者有更好的建議,歡迎演算法交流群交流,掃碼進群(如無法掃描進群,加微信:hungervalley 拉入群)。
點選掃碼進微信群