排序算法

基础排序算法：
- 冒泡排序
- 插入排序
- 选择排序
进阶排序算法：
- 归并排序
- 快速排序

冒泡排序

思路：

冒泡排序的过程，就是从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动。

每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。

一轮操作过程如下：

原数组

;[5, 3, 2, 4, 1]

第一轮

第一次比较，将第一个元素 5 和它相邻的元素 3 作比较，发现 5 比 3 大，故将 5 和 3 交换：

[3, 5, 2, 4, 1]
 ↑  ↑

第二次比较，将第二个元素 5 和第三个元素 2 作比较，发现 5 比 2 大，故将 5 和 2 交换：

[3, 2, 5, 4, 1]
    ↑  ↑

第三次：

[3, 2, 4, 5, 1]
       ↑  ↑

第四次：

[3, 2, 4, 1, 5]
          ↑  ↑

执行 4 次，将该元素 5，已经放置在对应合适的位置了，执行次数 n - 1 次。

第二轮

第一次：

[2, 3, 1, 4, 5]
 ↑  ↑

第二次：

[2, 1, 3, 4, 5]
    ↑  ↑

第三次：

[2, 1, 3, 4, 5]
       ↑  ↑

第四次：

[2, 1, 3, 4, 5]
          ↑  ↑

代码实现：

每轮将找到乱序中最大的元素，将这个元素放在对应位置（倒 1、倒 2...）

function bubbleSort(arr) {
  const len = arr.length
  // 外层循环用于控制从头到尾的比较+交换到底有多少轮
  for (let i = 0; i < len; i++) {
    // 内层循环用于完成每一轮遍历过程中的重复比较+交换
    for (let j = 0; j < len - 1; j++) {
      // 若相邻元素前面的数比后面的大
      if (arr[j] > arr[j + 1]) {
        // 交换两者
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

但是可以发现，在一轮排序后，最后一个元素已经是被排序好的，那么就只用排序剩余乱序的元素，可以做一下改进：

function betterBubbleSort(arr) {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

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

选择排序

思路：

选择排序的关键字是“最小值”：循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。

代码实现：

function selectSort(arr) {
  // 缓存数组长度
  const len = arr.length
  // 定义 minIndex，缓存当前区间最小值的索引，注意是索引
  let minIndex
  // i 是当前排序区间的起点
  for (let i = 0; i < len - 1; i++) {
    // 初始化 minIndex 为当前区间第一个元素
    minIndex = i
    // i是左边界，j是右边界
    for (let j = i; j < len; j++) {
      // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    // 如果 minIndex 对应元素不是目前的头部元素，则交换两者
    if (minIndex !== i) {
      ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
  return arr
}

插入排序

思路：

逐步构建有序序列：将数组分为已排序和未排序两部分，初始时已排序部分只有一个元素
逐个插入元素：从第二个元素开始，依次取出未排序部分的元素，将其插入到已排序部分的正确位置
寻找合适位置：在已排序部分中从后向前扫描，找到比当前元素小的元素位置，将该位置后的元素都向后移动一位
重复操作：对未排序部分的每个元素重复上述过程，直到所有元素都插入到正确位置

代码实现：

function insertSort(arr) {
  const len = arr.length
  // temp 用来保存当前需要插入的元素
  let temp
  // i用于标识每次被插入的元素的索引
  for (let i = 1; i < len; i++) {
    temp = arr[i]
    // j用于帮助 temp 寻找自己应该有的定位
    let j = i
    // 判断 j 前面一个元素是否比 temp 大
    while (j > 0 && arr[j - 1] > temp) {
      // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
      arr[j] = arr[j - 1]
      j--
    }
    // 循环让位，最后得到的 j 就是 temp 的正确索引
    arr[j] = temp
  }
  return arr
}

排序算法 ​

冒泡排序 ​

选择排序 ​

插入排序 ​

排序算法

冒泡排序

选择排序

插入排序