# 快速排序 (quickSort)
- 快速排序是对冒泡排序的一种改进, 第一趟排序先分成两份, 然后递归调用，继续二分。
- 快排属于分治法的一种，先把大问题分成各个小问题，再把小问题分成更小的问题。
### 简单算法实现
```js
const quickSort = (arr) => {
const len = arr.length
if (len < 2) return arr
else {
let flag = arr[0]
let left = []
let right = []
let temp
for (let i of arr) {
temp = arr[i]
if (temp < flag) left.push(temp)
else right.push(temp)
}
return quickSort(left).concat(flag, quickSort(right))
}
}
```
### 高级算法实现 (in-place)
```js
//交换函数
const swap = (arr, i, j) => {
const temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
//找到交换位置的函数
function findPivot(arr, start, end) {
let pivot = arr[end]
let index = start
for(let i = start; i < end; i ++) {
if(arr[i] < pivot) {
[arr[index], arr[i]] = [arr[i], arr[index]]
index ++
}
}
[arr[end], arr[index]] = [arr[index], arr[end]]
return index
}
function inPlace(arr, start, end) {
if(start > end) return
const index = findPivot(arr, start, end)
inPlace(arr, start, index - 1)
inPlace(arr, index + 1, end)
}
inPlace(arr, 0, arr.length - 1)
```
js数据结构与算法 -- 快速排序（quickSort） 简单算法与高级算法
