JavaScript 中几种快排的实现-Yinode Blog

实现 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

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

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

总结

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

JavaScript 中几种快排的实现

TOC

实现 1

实现 2

实现 3

总结

FEATURED TAGS