快速排序 (quickSort)

• 快速排序是对冒泡排序的一种改进, 第一趟排序先分成两份, 然后递归调用，继续二分。
• 快排属于分治法的一种，先把大问题分成各个小问题，再把小问题分成更小的问题。

简单算法实现

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)

//交换函数
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)