# 原理
对于一个数组，从中随机选择一个数字（一般选取第一个，当然也可以取中间的数，奇数与偶数取值不同，或者最后一个数为基准，这个不做要求），然后把整个数组中小于它的元素放在左侧，大于它的元素放在右侧，然后递归执行。
快速排序分三步：
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]))*/
```
