快速排序思想

1. 找到一个基准点;
2. 比该基准点值小的值移到其左侧, 比该基准点大的值移到其右侧;
3. 遍历左侧的值和右侧的值, 重复上述 1, 2 操作;

代码实现

function quickSort(arr) {
  if (arr.length === 0) {
    return []
  }
  const basicValue = arr[Math.floor((arr.length - 1) / 2)] // 随意取, 这里取中间
  const left = []
  const right = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < basicValue) {
      left.push(arr[i])
    }
    if (arr[i] > basicValue) {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat(basicValue, quickSort(right))
}

求快速排序时间复杂度

先记住 O(NlogN), 具体证明, someday to understand, o(╯□╰)o