> 引用：[https://www.cnblogs.com/chengxiao/p/6262208.html](https://www.cnblogs.com/chengxiao/p/6262208.html)
快速排序，正如其名，比其他分治排序一般要快。
思路：
1. 從數組中隨便取出一個數，把這個數當成一個“基數”
2. 循環數組中所有元素和這個“基數”對比，比它小的放在它左邊，比它大的放在它右邊
3. 再基數左右兩邊的元素看成兩個子數組，再分別對兩個子數組執行快速排序。。
如何確定哪個數做為“基數”？
我們可以使用 “三值取中法” 來確定基數。
思路：取數組中第1個、中間和最后一個元素三個值，對這三個數排序，把排在中間的數做為基數。（盡量讓這個數是所有值中排序中在中間位置的數）
對剩下的數進行循環處理：小于“基數”的放到左邊，大于基數的放到右邊：
現在基數（6）左邊都是小于它的，右邊都是大于它的。
然后在對基數（6）左右兩部分分成兩個子數列：
然后再對左右兩個子數列執行上面的過程排序：
# JavaScript
~~~
function quickSort(arr, left, right) {
if (left < right) {
/****** 1.處理 pivot \*/
// 計算中間值的下標
let mid = Math.floor((left + right) / 2)
// 左和中進行比較，大的放中間
if(arr[left] > arr[mid]) {
[arr[left],arr[mid]] = [arr[mid],arr[left]]
}
// 中和右進行比較，大的放右邊
if(arr[mid] > arr[right]) {
[arr[right],arr[mid]] = [arr[mid],arr[right]]
}
// 左和中進行比較，大的放中間
if(arr[left] > arr[mid]) {
[arr[left],arr[mid]] = [arr[mid],arr[left]]
}
// 把中間的（pivot）放到倒數第2個位置
[arr[mid],arr[right-1]] = [arr[right-1],arr[mid]]
/* 2.雙向循環把小的放到 pivot 左邊，大的放到 pivot 右邊 */
let pivot = right-1, // pivot 坐標
i = left, // 左指針
j = right - 1 // 右指針
while (true) {
//左指針小于 pivot 時元素不動繼續向后移動指針
while (arr[++i] < arr[pivot]) { }
// 右指針大于 pivot 時元素不動繼續向前移動指針
while (j > left && arr[--j] > arr[pivot]) { }
// 如果左右指針沒有相遇就交換，否則退出循環
if (i < j) {
[arr[i],arr[j]] = [arr[j],arr[i]]
} else {
break
}
}
// 將 pivot 放到中間，此時 pivot 左邊都是小于它的數，右邊都是大于它的數
if (i < right) {
[arr[i], arr[right-1]] = [arr[right-1],arr[i]]
}
// 根據 pivot 拆分成左右兩個子數組繼續快速排序
quickSort(arr, left, i-1)
quickSort(arr, i+1, right)
}
return arr
}
~~~
