# 原理
對于一個數組，從中隨機選擇一個數字（一般選取第一個，當然也可以取中間的數，奇數與偶數取值不同，或者最后一個數為基準，這個不做要求），然后把整個數組中小于它的元素放在左側，大于它的元素放在右側，然后遞歸執行。
快速排序分三步：
1. 選基準：在數據結構中選擇一個元素作為基準(pivot)
2. 劃分區：參照基準元素值的大小，劃分無序區，所有小于基準元素的數據放入一個區間，所有大于基準元素的數據放入另一區間，分區操作結束后，基準元素所處的位置就是最終排序后它應該所處的位置
3. 遞歸：對初次劃分出來的兩個無序區間，遞歸調用第 1步和第 2步的算法，直到所有無序區間都只剩下一個元素為止
# 代碼
```
// 取中間一個元素作為基準值
let quickSort = array => {
if (array.length <= 1) {
return array
}
let pivotIndex = Math.floor(array.length / 2)
let pivot = array.splice(pivotIndex, 1)[0]
let left = []
let right = []
for (let i = 0, length = array.length; i < length; i++) {
if (array[i] < pivot) {
left.push(array[i])
} else {
right.push(array[i])
}
}
return quickSort(left).concat(pivot, quickSort(right))
}
// 取第一個元素作為基準值
let quickSort = array => {
if (array.length <= 1){
return array
}
let pivot = array[0]
let left = []
let right = []
for(let i = 1; i < array.length; i++) {
if (array[i] > pivot) {
right.push(array[i])
} else {
left.push(array[i])
}
}
return quickSort(left).concat(pivot, quickSort(right))
}
/*console.log(quickSort([9, 4, 5, 1, 3, 2, 6, 8, 7]))*/
```
