說明
快速排序（QuickSort），又稱分割槽交換排序（partition-exchange sort），簡稱快排。快排是一種透過基準劃分區塊，再不斷交換左右項的排序方式，其採用了分治法，減少了交換的次數。它的基本思想是：透過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴或迭代進行，以此讓整個數列變成有序序列。
實現過程
在待排序區間找到一個基準點(pivot)，便於理解一般是位於陣列中間的那一項。 逐個迴圈陣列將小於基準的項放左側，將大於基準的項放在右側。一般透過交換的方式來實現。 將基準點左側全部項和基點右側全部項分別透過遞迴(或迭代)方式重複第1項，直到所有陣列都交換完成。
示意圖
quick1.png
解釋：以某個數字為基點，這裡取最右側的數字8，以基點劃分為兩個區間，將小於8的數字放在左側區間，將大於8的數字放在右側區間。再將左側區間和右側區間分別放到遞迴，按照最右側為基點，繼續分解。直到分解完畢，排序完成。這是其中一種常見的分割槽遞迴法，除了這種方式外，還有其他實現方式。
效能分析
平均時間複雜度：O(NlogN) 最佳時間複雜度：O(NlogN) 最差時間複雜度：O(N^2) 空間複雜度：根據實現方式的不同而不同，可以檢視不同版本的原始碼
程式碼
快排方式1, 新建陣列遞迴版本。無需交換，每個分割槽都是新陣列，數量龐大。
這個版本利用了JS陣列可變且隨意拼接的特性，讓每個分割槽都是一個新陣列，從而無需交換陣列項。 這個方式非常簡單易懂，但理論上來講不是完全意義上的快排，效率較差。
function quickSort1(arr) {
// 陣列長度為1就不再分解
console.log('origin array:', arr)
if (arr.length <= 1) {
return arr
}
var pivot
const left = []
const right = []
// 設定中間數，取最中間的項
var midIndex = Math.floor(arr.length / 2)
pivot = arr[midIndex]
for (var i = 0, l = arr.length; i < l; i++) {
console.log('i=' + i + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
// 當中間基數等於i時跳過。基數數待遞迴完成時合併到到新陣列。
if (midIndex === i) {
continue
}
// 當前數組裡面的項小於基數則新增到左側
if (arr[i] < pivot) {
left.push(arr[i])
// 大於等於則新增到右側
} else {
right.push(arr[i])
}
}
arr = quickSort1(left).concat(pivot, quickSort1(right))
console.log('sorted array:', arr)
// 遞迴呼叫遍歷左側和右側，再將中間值連線起來
return arr
}遞迴的過程
// 基於中間數進行遞迴分解： f([7, 11, 9, 10, 12, 13, 8]) / 10 \ f([7, 9, 8]) f([11, 12, 13]) / 9 \ / 12 \ f([7, 8]) f([]) f([11]) f[13] / 8 \ f([7]) f([]) [7] // 將遞迴後的最小單元和基數連線起來 // 得到：[7, 8, 9, 10, 11, 12, 13]
快排方式2, 標準分割槽遞迴版本。左右分割槽遞迴交換排序，無需新建陣列。
這個版本是最常見的標準分割槽版本，簡單好懂。先寫一個分割槽函式，依據基準值把成員項分為左右兩部分。基準值可以是數列中的任意一項，為了交換方便，基準值一般最左或最右側項。把小於基準值的放在左側，大於基準值的放在右側，最後返回分割槽索引。這樣就得到一個基於基準值的左右兩個部分。再將左右兩個部分，分別進行分割槽邏輯的遞迴呼叫，當左右值相等，也就是最小分割槽只有1項時終止。
// 分割槽函式，負責把陣列分按照基準值分為左右兩部分
// 小於基準的在左側，大於基準的在右側最後返回基準值的新下標
function partition(arr, left, right) {
// 基準值可以是left與right之間的任意值，再將基準值移動至最左或最右即可。
// 直接基於中間位置排序，則需要基於中間位置左右交換，參加基於中間位置交換的版本。
// var tmpIndex = Math.floor((right - left) / 2)
// ;[arr[left + tmpIndex], arr[right]] = [arr[right], arr[left + tmpIndex]]
var pivotIndex = right
var pivot = arr[pivotIndex]
var partitionIndex = left - 1
for (var i = left; i < right; i++) {
// 如果比較項小於基準值則進行交換，並且分割槽索引增加1位
// 也就是將大於基準值的全部往右側放，以分割槽索引為分割線
if (arr[i] < pivot) {
partitionIndex++
if (partitionIndex !== i) {
[arr[partitionIndex], arr[i]] = [arr[i], arr[partitionIndex]]
}
}
}
partitionIndex++;
[arr[partitionIndex], arr[pivotIndex]] = [arr[pivotIndex], arr[partitionIndex]]
return partitionIndex
}
// 分割槽遞迴版本，分割槽遞迴呼叫。
function quickSort2(arr, left, right) {
left = left !== undefined ? left : 0
right = right !== undefined ? right : arr.length - 1
if (left < right) {
var pivot = partition(arr, left, right)
quickSort2(arr, left, pivot - 1)
quickSort2(arr, pivot + 1, right)
}
return arr
}快排方式3, 標準左右交換遞迴版本。基於中間位置不斷左右交換，無需新建陣列。
此版本基於中間位置，建立雙指標，同時從前往後和從後往前遍歷，從左側找到大於基準值的項，從右側找到小於基準值的項。 再將大於基準值的挪到右側，將小於基準值的項挪到左側，直到左側位置大於右側時終止。左側位置小於基準位置則遞迴呼叫左側區間，右側大於基準位置則遞迴呼叫右側區間，直到所有項排列完成。
function quickSort3(arr, left, right) {
var i = left = left !== undefined ? left : 0
var j = right = right !== undefined ? right : arr.length - 1
// 確定中間位置，基於中間位置不停左右交換
var midIndex = Math.floor((i + j) / 2)
var pivot = arr[midIndex]
// 當左側小於等於右側則表示還有項沒有對比，需要繼續
while (i <= j) {
// 當左側小於基準時查詢位置右移，直到找出比基準值大的位置來
while (arr[i] < pivot) {
console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
i++
}
// 當前右側大於基準時左移，直到找出比基準值小的位置來
while (arr[j] > pivot) {
console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
j--
}
console.log(' left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
// 當左側位置小於等於右側時，將資料交換，小的交換到基準左側，大的交換到右側
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
// 縮小搜查範圍，直到左側都小於基數，右側都大於基數
i++
j--
}
}
// 左側小於基數位置，不斷遞迴左邊部分
if (left < j) {
console.log('left < j:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
quickSort3(arr, left, j)
}
// 基數位置小於右側，不斷遞迴右側部分
if (i < right) {
console.log('i < right:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
quickSort3(arr, i, right)
}
return arr
}快排方式4, 非遞迴左右交換版本。基於中間位置不斷左右交換，利用stack或queue遍歷。
這種方式標準左右交換遞迴版本的非遞迴版本，其原理一樣，只是不再遞迴呼叫，而是透過stack來模擬遞迴效果。這種方式效能最好。
function quickSort4(arr, left, right) {
left = left !== undefined ? left : 0
right = right !== undefined ? right : arr.length - 1
var stack = []
var i, j, midIndex, pivot, tmp
// 與標準遞迴版相同，只是將遞迴改為遍歷棧的方式
// 先將左右各取一個入棧
stack.push(left)
stack.push(right)
while (stack.length) {
// 如果棧內還有資料，則一併馬上取出，其他邏輯與標準遞迴版同
j = right = stack.pop()
i = left = stack.pop()
midIndex = Math.floor((i + j) / 2)
pivot = arr[midIndex]
while (i <= j) {
while (arr[i] < pivot) {
console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
i++
}
while (arr[j] > pivot) {
console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
j--
}
if (i <= j) {
tmp = arr[j]
arr[j] = arr[i]
arr[i] = tmp
i++
j--
}
}
if (left < j) {
// 與遞迴版不同，這裡當左側小於基數位置時新增到棧中，以便繼續迴圈
console.log('left < j:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
stack.push(left)
stack.push(j)
}
if (i < right) {
// 當右側大於等於基數位置時新增到棧中，以便繼續迴圈
console.log('i < right:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
stack.push(i)
stack.push(right)
}
}
return arr
}測試
(function () {
const arr = [7, 11, 9, 10, 12, 13, 8]
// 構建數列，可以任意構建，支援負數，也不限浮點
// const arr = [17, 31, 12334, 9.545, -10, -12, 1113, 38]
console.time('sort1')
const arr1 = arr.slice(0)
console.log('sort1 origin:', arr1)
console.log('\r\nquickSort1 sorted:', quickSort1(arr1))
console.timeEnd('sort1')
console.time('sort2')
const arr2 = arr.slice(0)
console.log('sort2 origin:', arr2)
console.log('\r\nquickSort2 sorted:', quickSort2(arr2))
console.timeEnd('sort2')
console.time('sort3')
const arr3 = arr.slice(0)
console.log('sort3 origin:', arr3)
console.log('\r\nquickSort3 sorted:', quickSort3(arr3))
console.timeEnd('sort3')
console.time('sort4')
const arr4 = arr.slice(0)
console.log('sort4 origin:', arr4)
console.log('\r\nquickSort4 sorted:', quickSort4(arr4))
console.timeEnd('sort4')
})()
/**
// 測試結果
jarry@jarrys-MacBook-Pro quicksort % node quick_sort.js
sort1 origin: [
7, 11, 9, 10,
12, 13, 8
]
origin array: [
7, 11, 9, 10,
12, 13, 8
]
i=0 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=1 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=2 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=3 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=4 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=5 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
origin array: [ 7, 9, 8 ]
i=0 midIndex=1 pivot=9 arr[]=7,9,8
i=1 midIndex=1 pivot=9 arr[]=7,9,8
i=2 midIndex=1 pivot=9 arr[]=7,9,8
origin array: [ 7, 8 ]
i=0 midIndex=1 pivot=8 arr[]=7,8
i=1 midIndex=1 pivot=8 arr[]=7,8
origin array: [ 7 ]
origin array: []
sorted array: [ 7, 8 ]
origin array: []
sorted array: [ 7, 8, 9 ]
origin array: [ 11, 12, 13 ]
i=0 midIndex=1 pivot=12 arr[]=11,12,13
i=1 midIndex=1 pivot=12 arr[]=11,12,13
i=2 midIndex=1 pivot=12 arr[]=11,12,13
origin array: [ 11 ]
origin array: [ 13 ]
sorted array: [ 11, 12, 13 ]
sorted array: [
7, 8, 9, 10,
11, 12, 13
]
quickSort1 sorted: [
7, 8, 9, 10,
11, 12, 13
]
sort1: 9.824ms
sort2 origin: [
7, 11, 9, 10,
12, 13, 8
]
partitioned arr= [
7, 8, 9, 10,
12, 13, 11
] partitionIndex: 1 left= [ 7 ] arr[partitionIndex]= 8 right= [ 8, 9, 10, 12, 13, 11 ] [
7, 8, 9, 10,
12, 13, 11
]
partitioned arr= [
7, 8, 9, 10,
11, 13, 12
] partitionIndex: 4 left= [ 9, 10 ] arr[partitionIndex]= 11 right= [ 11, 13, 12 ] [
7, 8, 9, 10,
11, 13, 12
]
partitioned arr= [
7, 8, 9, 10,
11, 13, 12
] partitionIndex: 3 left= [ 9 ] arr[partitionIndex]= 10 right= [ 10 ] [
7, 8, 9, 10,
11, 13, 12
]
partitioned arr= [
7, 8, 9, 10,
11, 12, 13
] partitionIndex: 5 left= [] arr[partitionIndex]= 12 right= [ 12, 13 ] [
7, 8, 9, 10,
11, 12, 13
]
quickSort2 sorted: [
7, 8, 9, 10,
11, 12, 13
]
sort2: 1.15ms
sort3 origin: [
7, 11, 9, 10,
12, 13, 8
]
arr[i] < pivot: i=0 j=6 pivot=10
left=0 right=6 i=1 j=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
arr[i] < pivot: i=2 j=5 pivot=10
arr[j] > pivot: i=3 j=5 pivot=10
arr[j] > pivot: i=3 j=4 pivot=10
left=0 right=6 i=3 j=3 midIndex=3 pivot=10 arr[]=7,8,9,10,12,13,11
left < j:recursion: left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
arr[i] < pivot: i=0 j=2 pivot=8
arr[j] > pivot: i=1 j=2 pivot=8
left=0 right=2 i=1 j=1 midIndex=1 pivot=8 arr[]=7,8,9,10,12,13,11
i < right:recursion: left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
arr[i] < pivot: i=4 j=6 pivot=13
left=4 right=6 i=5 j=6 midIndex=5 pivot=13 arr[]=7,8,9,10,12,13,11
left < j:recursion: left=4 right=6 i=6 j=5arr[]7,8,9,10,12,11,13
left=4 right=5 i=4 j=5 midIndex=4 pivot=12 arr[]=7,8,9,10,12,11,13
quickSort3 sorted: [
7, 8, 9, 10,
11, 12, 13
]
sort3: 0.595ms
sort4 origin: [
7, 11, 9, 10,
12, 13, 8
]
arr[i] < pivot: i=0 j=6 pivot=10arr[]=7,11,9,10,12,13,8
arr[i] < pivot: i=2 j=5 pivot=10arr[]=7,8,9,10,12,13,11
arr[j] > pivot: i=3 j=5 pivot=10arr[]=7,8,9,10,12,13,11
arr[j] > pivot: i=3 j=4 pivot=10arr[]=7,8,9,10,12,13,11
left < j:recursion: left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
i < right:recursion: left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
arr[i] < pivot: i=4 j=6 pivot=13arr[]=7,8,9,10,12,13,11
left < j:recursion: left=4 right=6 i=6 j=5arr[]=7,8,9,10,12,11,13
arr[i] < pivot: i=0 j=2 pivot=8arr[]=7,8,9,10,11,12,13
arr[j] > pivot: i=1 j=2 pivot=8arr[]=7,8,9,10,11,12,13
quickSort4 sorted: [
7, 8, 9, 10,
11, 12, 13
]
sort4: 0.377ms
*/連結
多種語言實現快速排序演算法原始碼：https://github.com/microwind/algorithms/tree/master/sorts/quicksort
其他排序演算法原始碼：https://github.com/microwind/algorithms
版权声明：除非特別標注，否則均為網際整理，轉載時請以連結形式注明文章出處。
tags：#JavaScript