javascript之快速排序

69 阅读 0 评论 46 点赞

我是靠谱客的博主英勇小伙，最近开发中收集的这篇文章主要介绍javascript之快速排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /*
      快速排序的中心思想:
          取出数组中最靠近中间的一个值,遍历数组,用数组里面的每一个值和这个基准值进行比较，
          小于这个基准值的放左边的数组，大于这个基准值的放右边的数组，递归遍历
          递归遍历的结束条件:当我数组中的值只有一项的时候,原封不动的返回该数组
          最后把左边的数组合并这个基准值以及右边的数组完成排序
    */
    const arr = [3, 4, 1, 2, 5, 7, 2, 9, 22, 1]
    function quickSort(arr) {
      // 判断arr的length是否只有1位了为结束条件
      if (arr.length <= 1) return arr
      // 取出基准值对应的下标
      const middIndex = Math.floor(arr.length / 2)
      // 根据下标在数组中把对应的值取出
      const middValue = arr.splice(middIndex, 1)[0]
      // 创建左边和右边的数组
      const leftArr = [], rightArr = []
      // 遍历数组
      for (let i = 0; i < arr.length; i++) {
        // 提取每一项放入一个变量，用于缓存数据，提高性能
        const value = arr[i]
        // 判断是否小于这个基准值.小的放左边的数组，大的放右边的数组
        value < middValue ? leftArr.push(value) : rightArr.push(value)
      }
      // 继续从左边的数组中取出一个中间值，在进行对比，递归
      const newLeftArr = quickSort(leftArr)
      // 继续从右边的数组中取出一个中间值，也进行对比，递归
      const newRightArr = quickSort(rightArr)
      // 递归完毕，进行合并返回即可
      return newLeftArr.concat([middValue], newRightArr)
    }
    const newArr = quickSort(arr)
    console.log(newArr)



  </script>
</body>

</html>