快速排序，代码实现，复杂度

[xszi]

由原文最常用的排序——快速排序总结而来：

6 1 2 7 9 3 4 5 10 8

首先在这个序列中随便找一个数作为基准数（一个作为参照的数）。为了方便，就让第一个数 6 作为基准数吧。

接下来，需要将这个序列中所有比 6 大的数放在 6 的右边，比 6 小的数放在 6 的左边

排序过程

分别从初始序列两端开始“探测”。先 右往左找到一个小于 6 的数停下，再 从左往右找一个大于 6 的数停下，然后交换他们。

定义序列左右两端的 ‘哨兵’ i和j，“探测”开始

第一次右边‘哨兵’找到 5，左边‘哨兵’找到 7 ，交换之后的序列如下:

6 1 2 5 9 3 4 7 10 8

第二次右边‘哨兵’找到 9，左边‘哨兵’找到 4 ，“探测”继续

交换之后的序列如下:

6 1 2 5 4 3 9 7 10 8

此时i和j相遇，探测结束

将基准数 6 和相遇位置的数 3 交换位置。得到序列如下：

3 1 2 5 4 6 9 7 10 8

现在基准数 6 已经归位。此时我们已经将原来的序列，以 6 为分界点拆分成了两个序列，左边的序列是3 1 2 5 4，右边的序列是 9 7 10 8。接下来还需要分别处理这两个序列。持续递归让数字归位....

最后得到我们最终排序完成的序列：

1 2 3 4 5 6 7 8 9 10

整个算法处理过程可以以下图来描述：

代码实现

let quickSort = (arr) => {
  quick(arr, 0 , arr.length - 1)
}

let quick = (arr, left, right) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    if(left < index - 1) {
      quick(arr, left, index - 1)
    }
    if(index < right) {
      quick(arr, index, right)
    }
  }
}

// 一次快排
let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i <= j) {

    // 左指针右移
    while(arr[i] < datum) {
      i++
    }

    // 右指针左移
    while(arr[j] > datum) {
      j--
    }

    // 交换
    if(i <= j) {
      swap(arr, i, j)
      i += 1
      j -= 1
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

算法复杂度

时间复杂度：O(nlogn) 空间复杂度：O(nlogn)

[xszi]

代码实现另一种写法：

const quickSort = (arr) => {
    if (arr.length < 2) return arr
    let leftArr = []
    let rightArr = []
    let pivot = arr[0]
    arr.forEach(element => {
        if (element < pivot) {
            leftArr.push(element)
        } else if (element > pivot) { 
            // 必须要加 if (element > pivot), 排除相等情况落入右边，引起Maximum call stack size exceeded
            rightArr.push(element)
        }
    })
    return [...quickSort(leftArr), pivot, ...quickSort(rightArr)]
}

• 时间复杂度：？？？
• 空间复杂度：？？？