排序算法---快速排序

快速排序思想

1. 从数组中选择一个元素作为基准点
2. 排序数组，所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。
3. 最后利用递归，将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。

快速排序代码实现

测试数组【6,5,4, 7,1】

第一轮：                                第二轮：                          第三轮：

对比值：6                              对比值 5                          对比值 4

左边 5，4，1                         左边 4，1                        左边 1

右边 7                                     右边 []                              右边 []

5,4,1,6,7                                  4,1,5,6,7                           1,4,5,6,7

function quickSort(arr) {
    if (arr.length <= 1) {
      return arr;
    }
    const left = []
    const right = []
    let temp = arr[0]
      for (let i = 1; i < arr.length; i++) {
        if (arr[i] > temp) {
          right.push(arr[i])
        } else {
          left.push(arr[i])
        }
      }
      return this.quickSort([...left]).concat(temp, this.quickSort(right))
}

快速排序复杂度

时间复杂度

快速排序的时间复杂度在平均情况下是O(nlogn)，但在最坏情况下可能达到O(n^2)

空间复杂度

快速排序的空间复杂度依赖于递归调用的深度，理想情况下为O(logn)，但在最坏情况下可能达到O(n)