姓名：朱嘉儀 學(xué)號：16020199053
轉(zhuǎn)載自https://zhuanlan.zhihu.com/p/46324489
【嵌牛導(dǎo)讀】隨著生活中算法應(yīng)用的越來越多，快速排序這種簡單有效的排序方法也變得非常有用。
【嵌牛鼻子】算法 快速排序
【嵌牛提問】快速排序是什么？怎樣使用快速排序？
【嵌牛正文】
一、原理解析
快速排序使用分治法策略來把一個序列分為兩個子序列。
步驟為：
1.從數(shù)列中挑出一個元素，稱為“基準(zhǔn)”，
2.重新排序數(shù)列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
3.遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
4.遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
以下是 JavaScript 版本的的代碼實現(xiàn)：
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 函數(shù)內(nèi)每次執(zhí)行新創(chuàng)建兩個數(shù)組，多次遞歸后會創(chuàng)建大量數(shù)組，在空間上存在"浪費"。我們可以在原數(shù)組上操作：
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
}
·對于一個數(shù)組，挑選最后一個值作為參考值(key)
·從數(shù)組的頭部開始掃描，如果值比參考值小，繼續(xù)往后掃描，直到掃描到的值(左值)比參考值大
·從數(shù)組的尾部(參考值的前一個)開始掃描，如果值比參考值大，繼續(xù)往前掃描，直到掃描到的值(右值)比參考值小
·此時交換掃描停止時的這兩個值
·繼續(xù)上面的邏輯，直到左值和右值相遇
·如果相遇時的值大于等于參考值，讓參考值和相遇值調(diào)換位置(一般情況)
·如果相遇時的值小于參考值，不調(diào)換，但 left 后移一位(特殊情況，如 [2, 1, 3, 4, 5])
講過上面的處理后，就會把數(shù)組變成以原數(shù)組末尾數(shù)字為分割（左邊都比它小，右邊都比它大）的數(shù)組。然后分別對參考值左側(cè)和右側(cè)通過類似的邏輯繼續(xù)處理。
二、效率測試
下面我們測試排序性能
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
}
經(jīng)瀏覽器測試，對于長度為10000的數(shù)組，排序約需要2.67ms(100次平均值)， 對于長度為100000的數(shù)組，排序約需要 94ms(100次樣本平均值)。
三、復(fù)雜度分析
時間復(fù)雜度為 O(nlogn)
