2rever的前端小站

js快速排序

Word count: 533 / Reading time: 3 min
2018/10/23 Share
  • 第二个工业级别的算法
  • 快速排序有就地排序和占用空间的排序
  • 暴力写法(经典写法)
  • 但是这个写法空间占用太大,所以不用这个写法
  • 可以通过快排找到数组中第K大的元素
  • 找到前K大的元素
  • 使用空间最少,速度最快
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function quickSort2(ary) {
if (ary.length < 2) {
return ary.slice()
}
var pivot = ary[Math.floor(Math.random() * ary.length)]//0到数组长度的值向下取整为0到数组长度-1
var left = []
var middle = []
var right = []
for(var i = 0; i<ary.length; i++) {
var val = ary[i]
if (val < pivot) {
left.push(val)
}
if (val === pivot) {
middle.push(val)
}
if (val > pivot) {
right.push(val)
}
}

return quickSort(left).concat(middle, quickSort(right))
}
  • 高级写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function partition2(ary, start = 0, end = ary.length - 1) {
var pivot = ary[start]

var i = start
var j = end

while(i < j) {
while(ary[++i] < pivot);
while(ary[--j] > pivot);
if (){

}
swap(ary, i, j)
}

if(){

}

swap(ary, i, start)

partition2(ary, start, i-1)
partition2(ary, i + 1, end)

}
  • 最高级写法,面试的时候经常会考到这样的写法,用这种写法满分
  • 火狐浏览器的源码就是这样写的
  • 这是最标准的写法,工业级写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//comparatop为高级函数,比如案例随机数或者比较函数
function partition(ary, comparator, start = 0, end = ary.length - 1, ) {
if (start >= end) { //要么是同一个元素,要么是之间没有其他元素了
return
}

var pivotIndex = Math.floor(Math.random() * (end - start + 1) + start)//这个减法刚好是要求的区间
var pivot = ary[pivotIndex]

swap(ary, pivotIndex, end) //换回来

for(var i = start - 1, j = start; j < end; j++) {
if (comparator(ary[j], pivot) < 0) { //i+1以前的元素都是小于等于中间数的 i 以后的元素都是大于中间数的
i++
swap(ary, i, j)
}
}

swap(ary, i + 1, end) //把那个随机中间数换回来
partition(ary, comparator, start, i)
partition(ary, comparator, i + 2, end)
return ary
}

function quickSort(ary, comparator = (a,b) => a - b) {
return partition(ary, comparator)
}
CATALOG