> 引用：[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
}
~~~
