js高效快速排序

110 阅读 0 评论 73 点赞

我是靠谱客的博主阳光音响，这篇文章主要介绍js高效快速排序，现在分享给大家，希望可以做个参考。

快速排序（Quicksort）是对冒泡排序的一种改进。

基本思路：

1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边

2.再按此方法对这两部分数据分别进行快速排序（递归进行）

3.不能再分后退出递归，并重新将数组合并

代码实现:

 function quickSort(arr) {
    // 如果数组元素长度小于等于1则直接返回
    if (arr.length <= 1) {
      return arr
    }
    // 找到基准
    let pivotIndex = Math.floor(arr.length / 2)
    //  找到基准，并把基准从原数组中删除
    let pivot = arr.splice(pivotIndex, 1)[0];
    //  定义左右数组
    let left = []
    let right = []
    // 比基准小的放在left 大的放在right
    arr.forEach(el => {
      if (el < pivot) {
        left.push(el)
      } else {
        right.push(el)
      }
    });
    return quickSort(left).concat([pivot], quickSort(right))
  }