javascript之快速排序

ゝ一纸荒年。 2022-12-05 04:53 109阅读 0赞

<!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>