快速排序与冒泡排序在数据规模不同情况下的执行时间差异

gist1.js

function bubbleSort(arr) {
  for (var j = 0; j < arr.length - 1; j++) {
    // 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数
    for (var i = 0; i < arr.length - 1 - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i]
        arr[i] = arr[i + 1]
        arr[i + 1] = temp
      }
    }
  }
  return arr
}

const quickSort = (function() {
  // 默认状态下的比较函数
  function compare(a, b) {
    if (a === b) {
      return 0
    }
    return a < b ? -1 : 1
  }

  function swap(array, a, b) {
    ;[array[a], array[b]] = [array[b], array[a]]
  }

  // 分治函数
  function partition(array, left, right) {
    // 用index取中间值而非splice
    const pivot = array[Math.floor((right + left) / 2)]
    let i = left
    let j = right

    while (i <= j) {
      while (compare(array[i], pivot) === -1) {
        i++
      }
      while (compare(array[j], pivot) === 1) {
        j--
      }
      if (i <= j) {
        swap(array, i, j)
        i++
        j--
      }
    }
    return i
  }
  // 快排函数
  function quick(array, left, right) {
    let index
    if (array.length > 1) {
      index = partition(array, left, right)
      if (left < index - 1) {
        quick(array, left, index - 1)
      }
      if (index < right) {
        quick(array, index, right)
      }
    }
    return array
  }
  return function quickSort(array) {
    return quick(array, 0, array.length - 1)
  }
})()

function random(min, max) {
  return Math.round(Math.random() * (max - min)) + min
}

function faker(count) {
  const arr = []
  for (let i = 0; i < count; i++) {
    const num = random(0, count)
    arr.push(num)
  }

  return arr
}

const arr1 = faker(50)
const arr2 = faker(50000)

console.time("bubbleSort time")
bubbleSort(arr1)
console.timeEnd("bubbleSort time")

console.time("quickSort time")
quickSort(arr1)
console.timeEnd("quickSort time")