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)
}

原文作者: 2rever

原文链接: https://2rever.cn/2018/10/23/js快速排序/

发表日期: October 23rd 2018, 11:14:36 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 24
2019
2018