排序

code
Prev Article
#algorithm

排序

JavaScript 原生提供了对数组元素排序的方法 arr.sort()，实现排序只需要数行代码即可实现

js
arr.sort((a,b) => {
    return a - b
})

但以面试为导向来看，一般会考察主要是以下 5 种算法的详细细节和优化：

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

排序算法的时间复杂度也是一个不能忽视的考点

在未经特别声明的情况下，都默认以「从小到大排列」为有序标准。

冒泡排序

j基本的冒泡排序的过程，就是每次从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动。每一轮操作，都会将这一轮中最大的元素放置到数组的末尾，仿佛气泡浮出水面一样，被「冒」到了数组顶部。这也是冒泡排序得名的原因。

假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。

Warning

因为每一次从头到尾的遍历都只能定位到一个元素的位置（第 n 轮可以将较大的第 n 个元素定位到倒数第 n 位上），因此元素有多少个，总的循环就要执行多少轮。

js
/**
 * basic bubble sort
 */
function bubbleSort(arr) {
  // 数组长度决定遍历次数
  const len = arr.length;
  // 外层循环控制遍历（从头到尾的比较+交换）次数
  for(let i=0;i<len;i++) {
    // 内层循环用于指示每一轮遍历两两元素的比较都是从数组的首位到[尾部-1]
    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;   // 最后返回排序好的数组
}

其实随着外层循环的进行，数组尾部的元素会渐渐变得有序，即走完第 n 轮循环的时候，数组的后 n 个元素就已经是有序的，对于已经有序的部分可以不再进行遍历比较操作，以降低时间复杂度。

js
function betterBubbleSort(arr) {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    // 对内层循环的范围作了限制，对于第 i 轮，两两元素的比较从数组的首位到[第 i-1 位]
    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
}
Tip

针对「最好」的情况，即在第一次冒泡的时候数组就完全有序，我们如果对这种作出特殊的标记，可以避免不必要的遍历，从而针对特殊的情况大大降低时间复杂度，将最好情况下的时间复杂度定向优化为 O(n)。

js
function betterBubbleSort(arr) {
    const len = arr.length;
    for(let i=0;i<len;i++) {
        // 加了一个标志位，用于记录是否一开始（虽然也需要进行一轮遍历才能判断）数组就完全有序
        let flag = false
        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]]
                // 只要发生了一次交换，就修改标志位
                flag = true
            }
        }
        // 若一次交换也没发生，则说明数组有序，直接放过
        if(flag == false)  return arr;
    }
    return arr
}

冒泡排序的时间复杂度分最好、最坏和平均来看：

  • 最好时间复杂度：它对应的是数组本身有序这种情况，只需要作比较（n-1 次），而不需要做交换，时间复杂度为 O(n)
  • 最坏时间复杂度： 它对应的是数组完全逆序这种情况，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n2)
  • 平均时间复杂度：涉及到一些概率论的知识，这里记住平均时间复杂度是 O(n2) 即可

选择排序

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

js
function selectSort(arr) {
  // 数组长度
  const len = arr.length;
  // 缓存当前区间最小值的索引
  let minIndex;
  // i 是当前排序区间的起点索引
  for (let i = 0; i < len; i++) {
    // 初始化 minIndex
    minIndex = i;
    // 从 i 开始遍历区间的元素
    for (let j = i; j < len; j++) {
      // 若当前元素比当前的最小值还小，就更新最小值的索引为 j
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // （如果最小值的索引不是当前区间的头部）对调元素，将最小值置于当前区间的头部
    if(minIndex !== i) {
      // 解构形式对调数组元素
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
  return arr
}

选择排序的最好情况也好，最坏情况也罢，都是要走内层循环作比较的（两者之间的区别仅仅在于元素交换的次数不同），因此的时间复杂度都对应两层循环消耗的时间量级 O(n2)。

Tip

选择排序将较小的元素排到区间的头部，然后每次缩小比较的区间；类似于冒泡排序（优化版）的步骤，只不过冒泡排序是将较大的元素排到区间的尾部。但是选择排序是在每一轮内循环结束后才进行依一次元素交换；但冒泡排序是频繁地进行两两元素交换的。

插入排序

插入排序所有的操作都基于一个这样的前提，当前元素前面的序列是有序的。然后需要插入的当前元素从这个有序序列的后面往前去寻找，在有序序列里找到正确位置插入。

Tip

由于前面序列是有序的（从小到大），当前元素从后往前寻找，只要比较得到有序序列其中一个元素比自己小（就可以保证有序序列前面的元素都比自己小，因此一般不需要遍历完整个有序序列），即可找到正确的插入位置。通过正确地定位当前元素在有序序列里的位置、不断扩大有序数组的范围，最终达到完全排序的目的。

排序过程演示：原始数组 [5, 3, 2, 4, 1]

  1. 首先，单个数字一定有序，因此数组首位的这个 5 可以看做是一个有序序列。
  2. 在这样的前提下， 可以选中第二个元素 3 作为当前元素，思考它和前面那个序列 [5] 之间的关系。很明显， 3 比 5 小，注意这里按照插入排序的原则，靠前的较大数字要为靠后的较小数字腾出位置
    js
    [暂时空出, 5, 2, 4, 1]
当前元素 3

    再往前看，发现没有更小的元素可以作比较了。那么现在空出的这个位置就是当前元素 3 应该待的地方 [3, 5, 2, 4, 1]。以上就完成了一轮插入，有序数组 [5] 现在变成了有序数组 [3, 5]
  3. 沿着这个思路，继续往下走，当前元素变成了 2。对比 2 和 5 的大小，发现 2 比 5 小。按照插入排序的原则，5要往后挪，给较小元素空出一个位置：
    js
    [3, 暂时空出, 5, 4, 1]
当前元素 2

    接着继续向前对比，遇到了 3。对比 3 和 2 的大小，发现 3 比 2 大。按照插入排序的原则，3要往后挪，给较小元素空出一个位置：
    js
    [暂时空出, 3, 5, 4, 1]
当前元素 2

    此时 2 前面的有序序列已经被对比完毕了。把 2 放到最终空出来的那个属于它的空位里去 [2, 3, 5, 4, 1]。以上完成了第二轮插入，有序数组变成了 [2, 3, 5]。
  4. 继续往下走，当前元素是 4。仍然是从后往前，首先对比 4 和 5 的大小，发现 4 比 5 小，那么 5 就要为更小的元素空出一个位置：
    js
    [2, 3, 暂时空出, 5, 1]
当前元素 4

    向前对比，遇到了 3。因为 4 比 3 大，符合从小到大的排序原则；同时已知当前这个序列是有序的，3 前面的数字一定都比 3 小，再继续向前查找就没有意义了。因此当前空出的这个坑就是 4 应该待的地方 [2, 3, 4, 5, 1]
  5. 以此类推，最后一个元素 1 会被插入到 [2, 3, 4, 5] 这个序列的头部去，最终数组得以完全排序 [1, 2, 3, 4, 5]
js
function insertSort(arr) {
  // 数组长度
  const len = arr.length;
  // 保存当前需要插入的元素
  let temp;
  // 遍历数组的元素
  for (let i = 0; i < len; i++) {
    // j 用于作为游标，寻找合适的插入索引位置，从当前元素开始（从后往前）
    let j = i;
    temp = arr[i];
    // 将游标不断从后往前移动，判断前面的元素是否比当前元素大
    while (j > 0 && arr[j - 1] > temp) {
      // 如果是，需要将 j 前面的一个元素后移一位（则将游标再往前移动），为 temp 让出位置
      arr[j] = arr[j-1];
      j--
    }
    // 直到遇到比 temp 小的元素或者到了数组头部，插入 temp
    arr[j] = temp;
  }
  return arr
}
  • 最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。
  • 最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n2)。
  • 平均时间复杂度：O(n2)

归并排序

归并排序是对分治思想的典型应用，它按照分治思想的框架进行排序：

  • 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
  • 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的，即对每个子数组进行排）。
  • 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组。

排序过程演示：原始数组 [8, 7, 6, 5, 4, 3, 2, 1]

  • 分解子问题
    1. 将数组整个对半分 [8, 7, 6, 5,| 4, 3, 2, 1]
    2. 对分割出的左右两个子数组各自对半分 [8, 7,| 6, 5,| 4, 3,| 2, 1]
    3. 对四个子数组再进行各自对半分割，使得每个子数组内都只有一个元素 [8,| 7,| 6,| 5,| 4,| 3,| 2,| 1]
  • 解决每个子问题
    1. 将规模为 1 的子数组两两合并为规模为 2 的子数组，合并时确保有序 [7, 8,| 5, 6,| 3, 4,| 1, 2]
    2. 接着将规模为 2 的按照有序原则合并为规模为 4 的子数组 [5, 6, 7, 8,| 1, 2, 3, 4]
  • 得出大问题的解 最后将规模为 4 的子数组合并为规模为 8 的数组，得到完整的有序的数组 [1, 2, 3, 4, 5, 6, 7, 8]
Tip

归并排序的核心是先通过分割再通过合并来实现，依托的是递归思想。

js
function mergeSort(arr) {
  // 数组长度
  const len = arr.length;
  // 处理递归边界
  if (len <= 1) {
    return arr
  }
  // 计算数组左右分割点
  const mid = Math.floor(len / 2);
  // 递归分割左子数组
  const leftArr = mergeSort(arr.slice(0, mid));
  // 递归分割右子数组
  const rightArr = mergeSort(arr.slice(mid, len));
  // 递归返回后，依次递归合并左右两个有序数组（每次递归合并都是按从小到大的，因此得到的都是有序数组）
  arr = mergeArr(leftArr, rightArr);
  return arr
}
function mergeArr(arr1, arr2) {
  // 初始化两个指针
  let i = 0,
    j = 0;
  // 初始化结果数组
  let res = [];
  // 数组 arr1 长度
  const len1 = arr1.length;
  // 数组 arr2 长度
  const len2 = arr2.length;
  // 合并两个有序数组，从小到大排列
  while(i<len2 && j<len2) {
    if(arr1[i]<arr2[j]) {
      res.push(arr1[i]);
      i++;
    } else {
      res.push(arr2[j]);
      j++;
    }
  }
  // 考虑到其中一个子数组首先被遍历完的情况
  // 需要将另一个子数组的剩余的有序元素直接拼接到结果数组中
  if(i<len1) {
    return res.concat(arr1.slice(i))
  } else {
    return res.concat(arr2.slice(j))
  }
  // 返回从小到大排列的有序数组
}
Tip

两个有序数组的合并使用了双指针法，可以参考 合并两个有序数组

我们把每一次切分+归并看做是一轮。对于规模为 n 的数组来说，需要切分 log(n) 次（实际是 log2n 次），因此就有 log(n) 轮。

每一轮中，切分动作都是小事情，只需要固定的几步：

js
 // 计算分割点
const mid = Math.floor(len / 2)
// 递归分割左子数组，然后合并为有序数组
const leftArr = mergeSort(arr.slice(0, mid))
// 递归分割右子数组，然后合并为有序数组
const rightArr = mergeSort(arr.slice(mid,len))

因此单次切分对应的是常数级别的时间复杂度 O(1)；而单次合并的时间复杂度为 O(n)（其中 n 是指两个子数组的元素个数和），因此决定归并排序时间复杂度的操作就是合并操作。

log(n) 轮对应 log(n) 次合并操作，因此归并排序的时间复杂度是 O(nlog(n))

快速排序

快速排序也是基于分而治之的原则实现的，但与归并排序的区别在于，它是直接在原有的数组内部进行排序。快速排序会将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

排序过程演示：原始数组 [5, 1, 3, 6, 2, 0, 7]

  1. 首先选取一个基准值（基准值的选择有多种方式，示例选取中间的值），并在左右两端分别设定指针。
js
[5, 1, 3, 6, 2, 0, 7]
         基准
                   ↑
 ↑
  1. 先移动左指针，直到找到一个不小于基准值的值为止；然后再移动右指针，直到找到一个不大于基准值的值为止。两端的指针满足条件时，停止移动的状态如下
js
[5, 1, 3, 6, 2, 0, 7]
         基准
                ↑
          ↑
  1. 如果左右指针没有越界（即左指针在右指针的右侧）就停下了（意味着基准值左边存在较大元素或右边存在较小元素），则交换左右指针的值，可以在划分的同时就让两边的元素「相对（与基准值）有序」，同时两个指针共同向中间走一步
js
[5, 1, 3, 0, 2, 6, 7]
             ↑ 基准
             ↑
Tip

可能存在交换的值就是基准值的情况，如示例，但不影响比较。

  1. 此时 2 比 6 小，故右指针不动，左指针继续前进，此时右指针所指的值不大于 6，左指针所指的值不小于 6，故两个指针都不再移动，而且指针越界*了。
js
[5, 1, 3, 0, 2, 6, 7]
               基准
             ↑
           right
                ↑
               left
  1. 此时可以基于左指针来划分左右两个子数组，对于左指针所指的数字来说，它左边的所有数字都比它小，右边的所有数字都比它大（也可能存在相等的情况）。由此就能够以左指针为轴心，划分出一左一右、一小一大两个子数组。
js
[5, 1, 3, 0, 2]
[6, 7]
  1. 针对两个子数组，重复执行以上操作，直到数组完全排序为止。
js
// 快速排序
function quickSort(arr, left = 0, right = arr.length - 1) {
  // 定义递归边界，若数组只有一个元素，则没有排序必要
  if (arr.length > 1) {
    // lineIdex 表示划分左右子数组的索引
    const lineIndex = partition(arr, left, right)
    // 如果左边子数组的长度不小于 1（如果子数组只有一个元素则 left = lineIndex-1），则递归快排该子数组
    if (left < lineIndex - 1) {
      // 左子数组以 lineIndex-1 为右边界
      quickSort(arr, left, lineIndex - 1)
    }
    // 如果右边子数组的长度不小于 1（如果子数组只有一个元素则 lineIndex = right），则递归快排该子数组
    if (lineIndex < right) {
      // 右子数组以 lineIndex 为左边界
      quickSort(arr, lineIndex, right)
    }
  }
  return arr
}
// 以基准值划分左右子数组的过程
function partition(arr, left, right) {
  // 默认取中间位置元素作为基准值
  let pivotValue = arr[Math.floor(left + (right - left) / 2)];
  // 初始化左右指针
  let i = left;
  let j = right;
  // 当左右指针不越界时，循环移动指针
  while (i <= j) {
    // 左指针所指元素若小于基准值，则一直右移左指针
    while (arr[i] < pivotValue) {
      i++
    }
    // 右指针所指元素若大于基准值，则一直左移右指针
    while (arr[j] > pivotValue) {
      j--
    }
    // 如果没有越界，但两指针已满足条件「停下」，意味着基准值左边存在较大元素或右边存在较小元素
    // 则直接对调指针所指元素，确保左右两侧的大小有序（相对于基准值），并分别往中间走一步，继续执行循环，直到越界
    if(i<=j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  }
  // 指针越界后，返回左指针作为划分子数组的索引
  return i;
}
// 快速排序过程中常常会在指针越界前交换左右指针的值，提取成一个独立的函数
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}

快速排序的时间复杂度的好坏，是由基准值来决定的：

  • 最好时间复杂度：每次选择基准值都刚好是当前子数组的中间数。这时可以确保每一次分割都能将数组分为两半，进而只需要递归 log(n) 次，和归并排序相似，最后结果也是 O(nlog(n))
  • 最坏时间复杂度：每次划分取到的都是当前数组中的最大值/最小值，把这种情况代入快排的思路中，此时快排已经退化为了冒泡排序，对应的时间复杂度是 O(n^2^)
  • 平均时间复杂度： O(nlog(n))

Previous Article

递归与回溯思想

Copyright © 2024 Ben

Theme BlogiNote

Icons from Icônes