前端算法系列 | 二、排序



默认从小到大，测试均在 leetcode 对应的数组排序题： 912. Sort an Array

概览

  • 冒泡排序
    循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。下一次循环继续上面的操作，不循环已经排序好的数。

  • 选择排序
    每次排序取一个最大或最小的数字放到前面的有序序列中。

  • 插入排序
    将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

  • 快速排序
    选择一个目标值，比目标值小的放左边，比目标值大的放右边，目标值的位置已排好，将左右两侧再进行快排。

  • 归并排序
    将大序列二分成小序列，将小序列排序后再将排序后的小序列归并成大序列。

  • 堆排序
    创建一个大顶堆，大顶堆的堆顶一定是最大的元素。交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。从后往前以此和第一个元素交换并重新构建，排序完成。

冒泡排序

时间复杂度：O(n^2)

  • 循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。这样一次循环之后最后一个数就是本数组最大的数。下一次循环继续上面的操作，不循环已经排序好的数。
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 bubbleSort(array) {
  for (let j = 0; j < array.length; j++) {
    for (let i = 0; i < array.length - j; i++) { // 只排后边的
      // 比较相邻数
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
      }
    }
  }
  return array;
}


// 优化：当一次循环没有发生冒泡，说明已经排序完成，停止循环。
function bubbleSort(array) {
  for (let j = 0; j < array.length; j++) {
    let finished = true
    for (let i = 0; i < array.length - j; i++) {
      // 比较相邻数
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        finished = false;
      }
    }
    if (finished) {
      return array
    }
  }
}
  • 运行时间: 5792 ms
  • 内存消耗: 42.3 MB

记录状态优化后：

  • 运行时间: 6244 ms
  • 内存消耗: 42.3 MB

选择排序

每次循环选取一个最小的数字放到前面的有序序列中。

时间复杂度：O(n^2)

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
function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) { // 每轮的初始最小值直到倒数第二个，最后一位当然不用再比了
    let minIndex = i

    for (let j = i + 1; j < array.length; j++) {
      // 通过暂存的最小索引，往后查找不断替换为比它更小的，找到最小
      if (array[j] < array[minIndex]) {
        minIndex = j
      }
    }
    // 一轮遍历后得到最小数，与当前位互换，再进行下一位
    [array[i], array[minIndex]] = [array[minIndex], array[i]]
  }
  return array
}


// 第二次循环会不断将更小的数往前提，因此不断替换元素而不是找到索引再替换，相对上边更耗时间
function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] > array[j]) {
        [array[i], array[j]] = [array[j], array[i]];
      }
    }
  }
  return array;
}
  • 运行时间: 1252 ms

  • 内存消耗: 42.5 MB

  • 运行时间: 5836 ms

  • 内存消耗: 40.8 MB

插入排序

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

时间复杂度：O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 从第二个开始，小于前一个值就往前移，
// 比前一个值大就原地待着，终止循环进入下一个 i
function InsertSort(array) {
  for (let i = 1; i < array.length; i++) {
    // 将用于比较的那个值的索引储存
    let compare = i
    for (let j = i - 1; j >= 0; j--) {
      if (array[compare] < array[j]) {
        [array[compare], array[j]] = [array[j], array[compare]]
        compare = j
      } else {
        break  // 终止循环
      }
    } 
  }

  return array
}
  • 运行时间: 1940 ms
  • 内存消耗: 42.5 MB

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

时间复杂度：O(nlogn)

实现步骤：

  1. 选择一个基准元素 target（一般选择第一个数）
  2. 将比 target 小的元素移动到数组左边，比 target 大的元素移动到数组右边
  3. 分别对 target 左侧和右侧的元素进行快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quickSort(array) {
  if (array.length < 2) {
    return array
  }

  const target = array[0]
  const left = []
  const right = []

  for (let i = 1; i < array.length; i++) {
    if (array[i] < target) {
      left.push(array[i])
    } else {
      right.push(array[i])
    }
  }

  return [...quickSort(left), target, ...quickSort(right)]
}
  • 运行时间: 124 ms
  • 内存消耗: 51.5 MB

参考链接

awesome-coding-js - 排序
图雀社区 - 前端学习数据结构与算法