date:
updated:

常见排序算法的js实现

js自带的排序方法 Array.prototype.sort(compareFunction)

MDN 文档 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
关于浏览器排序实现相关文章推荐 https://efe.baidu.com/blog/talk-about-sort-in-front-end/

这个方法会把数字转换为字符串再按照字典顺序进行比较, 传入一个函数可以改变其行为

compareFunction 接受两个参数, 表示进行比较的前一项和后一项, 返回一个数字, 用 ts 表示为 fn(a: any, b: any): number

若返回的数字大于0, 则第一个项排在第二个项后面; 其余情况(包括0), 第一个项排在第一个项前面

注意: 这个方法排序产生的结果是不稳定的, 内部实现方式也根据浏览器不同而有所差异

v8 源码中, 在数组长度较小时使用插入排序(稳定), 其余情况使用快速排序(不稳定) https://github.com/v8/v8/blob/ad82a40509c5b5b4680d4299c8f08d6c6d31af3c/src/js/array.js

1
2
3
4
5
6
7
8
9
10
// 711 行
// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.

// 763 行
// Insertion sort is faster for short arrays.
  if (to - from <= 10) {
    InsertionSort(a, from, to);
    return;
  }

例子

1
2
3
4
// 正序排列
const array = [1111, 111, 11]
array.sort((a, b) => a - b) // 倒序时返回 b - a
console.log(array) // [11, 111, 1111]

冒泡排序

时间复杂度 O(n) - O(n²), 稳定, 原地

按顺序比较每两个项, 若前一项大于后一项则交换这两个项, 最小的项最终会”冒泡”到最前面

1
2
3
4
5
6
7
8
9
10
11
12
function bubbleSort(arr) {
  for(let i = 0; i < arr.length - 1; i++) {
    for(let j = 0; j < arr.length - 1 - i; j++) {
      if(arr[j] > arr[j+1]) {
        let temp = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = temp
      } 
    } 
  }
  return arr
}

选择排序

时间复杂度 O(n²), 不稳定, 原地

从未排序的序列中找到最小的元素, 放在序列的起始位置, 重复这个过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function selectionSort(arr) {
  let minIndex, temp
  for(let i = 0; i < arr.length - 1; i++) {
    minIndex = i
    for(let j = i+1; j < arr.length; j++) {
      if(arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    temp = arr[minIndex]
    arr[minIndex] = arr[i]
    arr[i] = temp
  }
  return arr
}

插入排序

时间复杂度 O(n) - O(n²), 稳定, 原地

将第一个元素看作有序序列, 将后面的元素依次插入到前面的合适的位置形成新的有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertionSort(arr) {
  let preIndex, current
  for(let i = 1; i < arr.length; i++) {
    preIndex = i - 1
    current = arr[i] // 抽取一个数
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex] // 往前移
      preIndex--
    }
    arr[preIndex + 1] = current // 插回去
  }
  return arr
}

希尔排序

希尔排序是对插入排序的优化, 时间复杂度 O(nLogn), 不稳定, 原地

希尔排序先将序列按一定的步长分割成若干子序列进行插入排序, 再逐步缩减步长到1, 步长为1时即为一次插入排序; 希尔排序比插入排序每次循环只能移动一个元素相比, 效率得到了很大的提升 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 3个 for 一个 if
function shellSort(arr) {
  for(let d = Math.floor(arr.length / 2); d > 0; d = Math.floor(d / 2)) {
    for(let i = d; i < arr.length; i++) {
      for(let j = i - d; j >= 0; j -= d) {
        if(arr[j] > arr[j + d]) {
          let temp = arr[j + d]
          arr[j + d] = arr[j]
          arr[j] = temp
        }
      }
    }
  }
  return arr
}

归并排序

时间O(nlogn), 空间O(n), 稳定

归并排序采用分治法, 利用了额外的空间, 比较两个有序的数组并依次选出最小的数, 合并成一个有序的数组, 通过递归把”有序数组”缩小到只有一个元素的情况

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 自上而下的递归, 3个 while
function mergeSort(arr) {
  if(arr.length < 2) return arr
  let middle = Math.floor(arr.length / 2),
  left = arr.slice(0, middle),
  right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  let result = [] // 额外空间
  while(left.length && right.length) {
    if(left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    } 
  }
  while(left.length) {
    result.push(left.shift())
  }
  while(right.length) {
    result.push(right.shift())
  }
  return result
}

// 自下而上的迭代, 利用for循环取代递归
function iterativeMergeSort(arr) {
  for(let step = 1; step < arr.length * 2; step *= 2) {
    for(let left = 0; left + step < arr.length; left += step * 2) { // left + step >= arr.length 时只有左数组, 没有归并的必要
      let right = left + step
      let arrLeft = arr.slice(left, right), // 左数组
      arrRight
      // 右数组凑不够, 或刚刚够
      if(right + step >= arr.length) { 
        arrRight = arr.slice(right)
      } else {
        arrRight = arr.slice(right, right + step) // 右数组
      }
      let current = left
      while(arrLeft.length && arrRight.length) {
        if(arrLeft[0] <= arrRight[0]) {
          arr[current++] = arrLeft.shift()
        } else {
          arr[current++] = arrRight.shift()
        }
      }
      while(arrLeft.length) {
        arr[current++] = arrLeft.shift()
      }
      while(arrRight.length) {
        arr[current++] = arrRight.shift()
      }
    }
  }
  return arr
}

快速排序

时间nlogn - n², 空间logn, 原地, 不稳定

快速排序同样采用分治法, 根据一个基准值, 把一个数组分成两个, 比基准值大的和比基准值小的, 再递归地执行这个过程; 它的特点如其名, 平均效率最高

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
28
29
30
31
function quickSort(arr, left, right) {
  let partitionIndex
  left = typeof left === 'number' ? left : 0 // 初始只传入一个 arr
  right = typeof right === 'number' ? right : arr.length - 1
  
  if(left < right) { 
    partitionIndex = partition(arr, left, right) // 分组, 获取中间的基准值, 左边的比基准值小, 右边的比基准值大
    quickSort(arr, left, partitionIndex - 1) // 快排左数组
    quickSort(arr, partitionIndex + 1, right) // 快排右数组
  } // 其他情况说明已经切分到最小单位了, 直接返回
  return arr
}

function partition(arr, left, right) {
  let pivot = left, // 基准
  index = pivot + 1
  for(let i = index; i <= right; i++) {
    if(arr[i] < arr[pivot]) {
      swap(arr, i, index) // 把较小数放在基准数的后面
      index ++ // index 前移, 避开刚才置换过来的较小数      
    }
  }
  swap(arr, pivot, index - 1) // 基准数与最后被置换的较小数交换位置, 这样基准数左边的数都比基准数小
  return index - 1 // 返回基准数当前的位置
}

function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

堆排序

时间复杂度nlogn, 原地, 不稳定

堆排序是利用堆这种数据结构, 把数组理解成一个完全二叉树, 把这棵完全二叉树做成大顶堆(父节点的值大于等于子节点的值); 交换堆顶的数和堆尾的数(把最大的数放到了最后面); 无视最后一个数(认为数组长度-1), 对堆顶进行一次大顶堆的调整, 重复上面两个过程直到数组长度为1

数组就会从堆尾开始变得有序, 大顶堆的话就会排列成递增的数组

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 初始化建立大顶堆
function buildMaxHeap(arr) {
  for(let i = Math.floor(arr.length / 2); i >= 0; i--) { // 从有叶节点的节点开始进行堆调整, length / 2 正好是最后一个有叶节点的节点
    heapify(arr, i, arr.length)
  }
  return arr
}

// 堆调整
function heapify(arr, i, len) {
  let left = 2 * i + 1, // 左儿子
  right = 2 * i + 2, // 右儿子
  largest = i
  
  if(left < len && arr[left] > arr[largest]) {
    largest = left
  }

  if(right < len && arr[right] > arr[largest]) {
    largest = right
  }
  
  if(largest !== i) {
    swap(arr, i, largest)
    heapify(arr, largest, len)
  }
}

function swap(arr, i, j) {
  let temp = arr[j]
  arr[j] = arr[i]
  arr[i] = temp
}

function heapSort(arr) {
  arr = buildMaxHeap(arr)
  for(let i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i) // 交换堆顶和堆尾
    heapify(arr, 0, i) // 调整堆顶
  }
  return arr
}

计数排序

具有线性时间复杂度, 但要求输入的数据是有确定范围的整数(0 - k), 局限性较大; 以最大的整数+1为总长度创建一个数组(具有0-k下标的数组), 用数组的下标为输入的整数进行计数, 每有一个数k就对下标为k的元素+1, 最终从小到大把数重新列出来; 因此会消耗大量空间

计数排序的时间复杂度为 n+k, 空间复杂度为 O(k), 是稳定的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function countingSort(arr, maxValue) {
  let bucket = new Array(maxValue + 1),
  sortedIndex = 0,
  arrLen = arr.length,
  bucketLen = maxValue + 1
  
  for(let i = 0; i < arrLen; i++) {
    if(!bucket[arr[i]]) {
      bucket[arr[i]] = 0
    }
    bucket[arr[i]]++ // 记录下这个数有多少个
  }
  
  for(let j = 0; j < bucketLen; j++) {
    while(bucket[j] > 0) {
      arr[sortedIndex++] = j
      bucket[j]--
    }
  }
  return arr
}

桶排序

是计数排序的优化版本, 用一个桶(可以装多个元素)取代计数排序中的一个萝卜一个坑的计数方式, 比如0-9放在第一个桶中, 10-19放在第二个桶中, 对每个桶进行分别排序, 再合并, 是否快速关键在于元素能否均匀地分配到各个桶中, 分配的越均匀, 效率越高

设有 k 个桶, 则平均时间复杂度为 n + k, 但最坏的情况(所有数都集中在一个桶中)时间复杂度达到 n², 是稳定的排序算法

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
28
29
30
function bucketSort(arr, bucketSize = 5) { // bucketSize: 每个桶里面装多少个数据 
  if(!arr.length) return arr
  // 找到数组中的最小值和最大值
  let min = arr[0], max = arr[0]
  for(let i = 1; i < arr.length; i++) {
    if(arr[i] < min) min = arr[i]
    else if(arr[i] > max) max = arr[i]
  }
  
  // 初始化桶
  let bucketCount = Math.floor((max - min) / bucketSize) + 1 // 有多少个桶
  let buckets = new Array(bucketCount)
  for(let i = 0; i < buckets.length; i++) {
    buckets[i] = []
  }
  // 分配元素到各个桶中
  for(let i = 0; i < arr.length; i++) {
    buckets[Math.floor(
      (arr[i] - min) / bucketSize
    )].push(arr[i]) // 分配到桶中
  }
  let resultArr = []
  for(let i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]) // 对每个桶进行排序
    for(let j = 0; j < buckets[i].length; j++) { // 排序之后就可以直接插入
      resultArr.push(buckets[i][j])
    }
  }
  return resultArr
}

基数排序

将整数按位切割成不同的数字, 然后按每个位数分别比较, 设 k 是整数的位数, 时间复杂度为 kn, 稳定的排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function radixSort(arr, maxDigit) { // maxDigit: 最大位数
  let counter = []
  let mod = 10, dev = 1
  for(let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { // 按位循环: k
    for(let j = 0; j < arr.length; j++) { // 分配到桶里面: n
      let bucket = parseInt((arr[j] % mod) / dev)
      if(counter[bucket] == null) {
        counter[bucket] = []
      }
      counter[bucket].push(arr[j])
    }
    let pos = 0
    for(let j = 0; j < counter.length; j++) { // 写回数组
      if(counter[j]) {
        while(counter[j].length) {
          arr[pos++] = counter[j].shift()
        }
      }
    }
  }
  return arr
}

示例数组

1
let arr = [2, 4, 7, 9, 5, 6, 1, 3, 8]

参考文章

vue2高阶组件 Next →