第97题 实现快速排序并说明时间复杂度

思路分析

• 找到中间位置midValue
• 遍历数组，小于midValue放在left，否则放在right
• 继续递归，最后concat拼接返回
• 使用splice会修改原数组，使用slice不会修改原数组（推荐）
• 一层遍历+二分的时间复杂度是O(nlogn)

快速排序（使用 splice）

    /**
     * 快速排序（使用 splice）
     * @param arr:number[] number arr
     */
    function quickSort1(arr) {
      const length = arr.length
      if (length === 0) return arr
    
      // 获取中间的数
      const midIndex = Math.floor(length / 2)
      const midValue = arr.splice(midIndex, 1)[0] // splice会修改原数组，传入开始位置和长度是1
    
      const left = []
      const right = []
    
      // 注意：这里不用直接用 length ，而是用 arr.length 。因为 arr 已经被 splice 给修改了
      for (let i = 0; i < arr.length; i++) {
        const n = arr[i]
        if (n < midValue) {
          // 小于 midValue ，则放在 left
          left.push(n)
        } else {
          // 大于 midValue ，则放在 right
          right.push(n)
        }
      }
    
      return quickSort1(left).concat([midValue], quickSort1(right))
    }

快速排序（使用 slice）

    /**
     * 快速排序（使用 slice）
     * @param arr number arr
     */
    function quickSort2(arr) {
      const length = arr.length
      if (length === 0) return arr
    
      // 获取中间的数
      const midIndex = Math.floor(length / 2)
      const midValue = arr.slice(midIndex, midIndex + 1)[0] // 使用slice不会修改原数组，传入开始位置和结束位置
    
      const left = []
      const right = []
    
      for (let i = 0; i < length; i++) {
        if (i !== midIndex) { // 这里要忽略掉midValue
          const n = arr[i]
          if (n < midValue) {
            // 小于 midValue ，则放在 left
            left.push(n)
          } else {
            // 大于 midValue ，则放在 right
            right.push(n)
          }
        }
      }
    
      return quickSort2(left).concat([midValue], quickSort2(right))
    }

    // 功能测试
    const arr1 = [1, 6, 2, 7, 3, 8, 4, 9, 5]
    console.info(quickSort2(arr1))

    // 性能测试
    
    // 快速排序（使用 splice）
    const arr1 = []
    for (let i = 0; i < 10 * 10000; i++) {
      arr1.push(Math.floor(Math.random() * 1000))
    }
    console.time('quickSort1')
    quickSort1(arr1)
    console.timeEnd('quickSort1') // 74ms
    
    // 快速排序（使用 slice）
    const arr2 = []
    for (let i = 0; i < 10 * 10000; i++) {
      arr2.push(Math.floor(Math.random() * 1000))
    }
    console.time('quickSort2')
    quickSort2(arr2)
    console.timeEnd('quickSort2') // 82ms

    // 单独比较 splice 和 slice
    
    const arr1 = []
    for (let i = 0; i < 10 * 10000; i++) {
      arr1.push(Math.floor(Math.random() * 1000))
    }
    console.time('splice')
    arr1.splice(5 * 10000, 1)
    console.timeEnd('splice') // 0.08ms
    
    const arr2 = []
    for (let i = 0; i < 10 * 10000; i++) {
      arr2.push(Math.floor(Math.random() * 1000))
    }
    console.time('slice')
    arr2.slice(5 * 10000, 5 * 10000 + 1)
    console.timeEnd('slice') // 0.008ms