其实也就是前段时间点阮一峰快排事件,正好去看看大家的实现,在这里记录一下,并写一下注释

实现 1

特点

  • 简单 智力经济
  • 性能较差
  • 加随机化比较方便 只要把取 pivot 的过程改成随机化就可以
  • 额外的空间
function quick_sort1(arr) {
  if (!arr || arr.length < 2) return arr
  const pivot = arr.pop()
  const left = arr.filter(v => v <= pivot)
  const right = arr.filter(v => v > pivot)
  return quick_sort1(left).concat([pivot], quick_sort1(right))
}

实现 2

特点

  • 简单
  • 性能方面从利用 filter 变成了 for 循环比较 性能会有一定优势
  • 同样易于加入随机化技术
  • 额外的空间
function quick_sort2(arr) {
  if (arr.length <= 1) return arr

  let pirvotIndex = Math.floor(arr.length / 2)
  let pirvot = arr.splice(pirvotIndex, 1)[0]

  let left = []
  let right = []

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pirvot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quick_sort2(left)
    .concat([pirvot])
    .concat(quick_sort2(right))
}

实现 3

特点

  • 无需额外的空间
  • 更高的性能
  • 添加随机化相对困难
function quick_sort3(arr, start, end) {
  let mid = arr[start],
    p1 = start,
    p2 = end

  while (p1 < p2) {
    swap(arr, p1, p1 + 1)
    while (compare(arr[p1], mid) >= 0 && p1 < p2) {
      swap(arr, p1, p2--)
    }
    p1++
  }

  if (start < p1 - 1) quick_sort3(arr, start, p1 - 1)
  if (p1 < end) quick_sort3(arr, p1, end)
}

最后我测试了一下这几个排序的性能,100000 个项的随机数数组

console.time('fill-map-create')
const testArr = Array(100000)
  .fill(1)
  .map(v => Math.floor(Math.random() * 100))
console.timeEnd('fill-map-create')

let testArr2 = []
console.time('for-create')
for (let i = 0; i < 100000; i++) {
  testArr2.push(Math.floor(Math.random() * 100))
}
console.timeEnd('for-create')

console.time('quick-sort1')
quick_sort1(testArr)
console.timeEnd('quick-sort1')

console.time('quick-sort2')
quick_sort2(testArr)
console.timeEnd('quick-sort2')

console.time('quick-sort3')
quick_sort3(testArr, 0, testArr.length - 1)
console.timeEnd('quick-sort3')

结果

fill-map-create: 19.049ms
for-create: 7.286ms
quick-sort1: 1857.542ms
quick-sort2: 416.660ms
quick-sort3: 99.450ms

还顺便看了一下创建方式对性能的影响

当然 以上的几种肯定不能涵盖所有的实现,一定有更快或者是更慢的实现。

总结

算法真的很重要,平时咱们可以写的易于阅读简单化,但是一但遇到大量数据的情况,就一定要小心谨慎。