快速排序过程分析

发表于 更新于 分类于 ， 本文字数： 346 阅读时长 ≈ 1 分钟

浅析过程

快速排序的原理是，通过定一种中间基准值。与这个基准值进行比较，即可区分成比该值大的一组，以及比该值小的一组。然后继续对区分好的数组进去取基准，在进行比较。直到该数组无法切分后，再将一层层向上合并，最终返回结果。

时间复杂度为 O(nlogn)

代码实现思路

  1. 判断传进来的数组长度是否可以分割，也是用于终止递归的一个判断条件
  2. 对数组获取中间值，并抽离出来
  3. 定义两个数组，分别保存左右两边的数据集。对数组进行循环，比中间值大的存到right中，比中间值小的存到left中。
  4. 进行递归，分别在对left和right的数组的值，再次进行切割判断回到第一步
  5. 当所有数值都分割并比较结束后，在将值从下往上合并回来，并返回出去

代码实现

1
2
3
4
5
6
7
8
9
10
11
const quickSort = arr => {
  if(arr.length <= 0) return arr
  const middleNumber = arr.splice(Math.floor(arr.length / 2), 1)[0]
  const left = []
  const right = []
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] > middleNumber) right.push(arr[i])
    else left.push(arr[i])
  }
  return quickSort(left).concat(middleNumber, quickSort(right))
}

图例

image.png

画的有点丑，以上均是个人理解。如果有哪些不对的地方欢迎指出~