前言

哈喽大家好！我是嘟老板，在外漂泊多年，终是打算回老家找个工作安定下来，最近在各种做面试准备，顺便整理一波分享分享，希望能对大家有所帮助。今天要聊的主题是 解读排序算法。

阅读本文您将收获：

了解几种常见的排序算法，包括算法设计、实现过程及效率分析等。等等...

本文内的排序算法，都是以 升序 排列。

冒泡排序

冒泡排序是一种基本排序算法，属于 ”简单排序“ 的范畴。

设计思路

假设现有一个待排序数组 arr - [4,2,7,1]，具体步骤如下：

遍历待排序数组 arr。

两个指针指向数组开头和其相邻的元素，即 4 和 2 的位置，比较他们的值。

若左边的值大于右边的值，则交换两个元素的位置，否则跳过。示例中左边的 4 大于右边的 2，交换位置。

把指针后移一位，指向 4 和 7 的位置。

重复步骤 (2)-(4)，直到到达数组末尾或已经排好序的值(后续说明)，完成数组的第一次遍历。示例中结束第一次遍历后的结果如下：

第一次遍历结束，最大的数 7 移动到了最右侧，所以 7 就是已经排好序的值，后续无需再进行任何比较，因为没有比它大的数了

把两个指针重新移回数组开头，重复步骤 (2)-(5)，不断遍历数组，只要没有元素需要交换，表示排序完毕。最终结果：

编码实现

完整代码如下：

function bubbleSort(arr) {
  let unsortedUntilIndex = arr.length - 1;
  let sorted = false
  while (!sorted) {
    sorted = true
    for (let i = 0; i < unsortedUntilIndex; i++) {
      if (arr[i] > arr[i+1]) {
        [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
        sorted = false
      }
    }
    unsortedUntilIndex--
  }
  return arr
}

代码解读

我们来逐行解读一下。

定义两个变量 unsortedUntilIndex，sorted，其中 unsortedUntilIndex 对应的元素位置索引，该值后面的元素，表示已经排序完成的元素，无需再次比较；sorted 表示完全排序完成，可以返回结果了。

while (!sorted)，以 sorted 作为循环条件，只要 sorted 为 false，就继续循环。

sorted = true，每次循环都假定已经排序完成，若后续有需要交换的元素，再将 sorted 置为 false。

for (let i = 0; i < unsortedUntilIndex; i++) { // ... }，遍历 unsortedUntilIndex 之前的所有元素，unsortedUntilIndex 后的元素已排序完成，无需再次比较。

若索引 i 处的元素大于 i+1 处的元素，交换位置，将值大的元素调整到后面。

if (arr[i] > arr[i+1]) {
    [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
    sorted = false
}

unsortedUntilIndex-- 每次遍历结束，则完成一个元素的冒泡，unsortedUntilIndex 位置向前移动一位，即 -1。return arr while 循环结束，表示排序完成，返回排序后的结果。换一种实现

冒泡排序不止一种实现方式，再来一个使用双循环实现的冒泡排序，供小伙伴参考。

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]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  return arr;
}

效率解读

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

选择排序设计思路

还是那个数组 arr - [4,2,7,1]，具体步骤如下：

从左到右检查数组的每一个元素，找到最小的元素，记录下其索引；

将最小的元素与最初遍历的元素交换位置，如第一次循环，最初遍历的元素是 4，最小元素是 1，将 1 和 4 交换位置；

遍历位置向后移动一个位置，重复以上步骤，直到最初遍历的元素是数组的最后一个元素，则排序完成；

编码实现

完整代码如下：

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex!== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
  return arr
}

代码解读

我们来逐行解读一下。

for (let i = 0; i < arr.length; i++) { // ... }，遍历数组，每遍历一次就对数组中未排序元素进行一次检查，从第一个元素到倒数第二个元素，最后一个元素无需处理，因为此时满足最初遍历的位置是最后一个元素的条件，已排序完成。

let minIndex = i，定义变量，存储一次检查中，最小值对应的索引。

for (let j = i; j < arr.length; j++) { // ... } 遍历数组中未排序的部分，执行元素检查。

若当前值小于目前最小值，则将最小值索引 minIndex 更新成当前索引。

if (arr[j] < arr[minIndex]) {
    minIndex = j
}

完成一次检查后，判断最小值是否已位于正确的位置，即若 minIndex === i，无需交换位置，否则，交换最初遍历元素 arr[i] 与最小值 arr[minIndex] 的位置。

if (minIndex!== i) {
  [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}

return arr，最后返回结果 arr。效率解读

时间复杂度 O(n^2)。确切的说是 O(n^2/2)，但是大 O 记法忽略常数项，所以记作 O(n^2)，选择排序相比冒泡排序，同数据量的情况下，效率快大约 1 倍。

插入排序设计思路

还是那个数组 arr - [4,2,7,1]，具体步骤如下：

在首次遍历中，暂时移除索引为 1 处的元素，存储在临时变量中。这样数组中就会有一个空位，即索引为 1 处的位置。

将空位左边的值与临时变量进行比较，若左边的值大于临时变量，则将其右移。目前空位左边的值为 4，大于临时变量 2，所以将 4 位置右移，原本 4 的位置变成空位。

若空位左边没有任何值，或左侧的值小于临时值，位移结束。

把临时变量插入空位。

空位的位置向后移动一位，重复步骤 (1)-(3)，直到空位移动到最后一个索引，排序完成。编码实现

完整代码如下：

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {

    const tempValue = arr[i]
    let position = i - 1
    while (position >= 0 && arr[position] > tempValue) {
      arr[position + 1] = arr[position]
      position--
    }
    arr[position+1] = tempValue
  }
  return arr
}

代码解读

我们来逐行解读一下。

for (let i = 1; i < arr.length; i++) { // ...}，循环数组，代表空位移动的过程，从索引 1 出开始。

const tempValue = arr[i]，定义临时变量 tempValue，存储当前循环中空位对应的值。

let position = i - 1，定义位置变量 position，指向空位左侧的元素位置。

只要空位左侧存在元素，且其值大于临时值，将左侧元素右移，即将 position 位置的值移动到 position + 1 处，并且 position 减 1，开启下一次左侧值的对比。

while (position >= 0 && arr[position] > tempValue) {
  arr[position + 1] = arr[position]
  position--
}

arr[position+1] = tempValue，空位左侧全部的值都对比完成后，将临时变量插入到空位处。因为 position 指向空位左侧的位置，所以空位处的索引为 position + 1。return arr，空位移动循环结束后，返回结果。效率解读

时间复杂度 O(N^2)。

快速排序

快速排序通过递归实现。

很多编程语言都内置了排序函数，很多排序函数的底层实现都是使用 快速排序 算法，比如 V8 实现的 Array.sort，默认情况下就是用的 快速排序。

设计思路

为方便演示，测试数据 arr 改为 [4,2,7,1,3]。

快速排序可以总结为两个步骤：分区和排序，你可能会比较好奇，分区是啥玩意？别着急，我们继续往下看。

分区

分区就是将待排序数组以某个基准值(方便起见，通常使用数组最后一个元素) 分为左右两个区，左侧区内的元素都小于基准值，右侧区内的元素都大于基准值。

具体步骤如下：

以数组最后一个元素作为基准值，创建两个指针，左指针 leftPointer 指向数组最左边的元素，右指针 rightPointer 指向基准值以外，最右边的元素。

左指针向右移动，每次移动一位，直至遇到大于或等于基准值时，停止移动；

右指针向左移动，每次移动一位，直到遇到小于或等于基准值时，或到达数组开头，停止移动；

右指针移动停止后，若左指针遇到(或超过了)右指针，前往第 (5) 步，否则交换左右指针指向的元素，重复执行 (2)-(4) 步；

交换基准值和左指针指向的数；

分区后，基准值左边的数都比它小，右边的数都比它大，意味着基准值所处的位置是排序正确的。

结合示例理解一下：

示例中 arr 最后一个元素 3 作为基准值，leftPointer 指向第一个元素 4，rightPointer 指向除去 3 外的最后一个元素 1。

比较左指针指向的元素和基准值，4 大于 3，左指针停止移动；

比较右指针指向的元素和基准值，1 小于 3，右指针停止移动；

此时左指针和右指针没有相遇，交换左右指针的元素，交换后的结果如下：

接下来左指针继续移动，指向 2, 2 小于 3，左指针继续向右移动，移动到 7，7 大于 3，左指针停止移动。

接下来右指针继续向左移动，指向 7，7 大于 3，右指针继续向左移动，指向 2,2 小于 3，右指针停止移动。

此时左指针超过了右指针，交换左指针指向的元素和基准值，分区结束，分区后的结果如下：

此时基准值 3 左侧的元素均小于 3，右侧的元素均大于 3，分区完成。

排序

实际上分区的过程已经在排序了，只不过是一次排序的过程。

排序步骤具体如下：

通过一次分区，将基准值调整到正确的位置。

然后在对基准值左、右两侧的子数组进行分区，递归执行步骤 (1)-(2)，不断进行分区。

若某个子数组没有元素或只有一个元素，表示左侧排序完成，停止递归；

编码实现分区

完整代码如下：

function partition(arr, leftPointer, rightPointer) {
  const pivotIndex = rightPointer
  const pivot = arr[pivotIndex]
  rightPointer--
  while(true) {
    while (arr[leftPointer] < pivot) {
      leftPointer++
    }
    while (arr[rightPointer] > pivot) {
      rightPointer--
    }
    if (leftPointer >= rightPointer) {
      break
    } else {
      [arr[leftPointer], arr[rightPointer]] = [arr[rightPointer], arr[leftPointer]]
      leftPointer++
    }
  }
  [arr[pivotIndex], arr[leftPointer]] = [arr[leftPointer], arr[pivotIndex]]
  return leftPointer
}

代码解读

我们来逐行解读一下：

const pivotIndex = rightPointer;const pivot = arr[pivotIndex]，定义两个个变量：

rightPointer--，右指针指向挨着基准值的左侧元素。

while(true) { // ... }，无限循环，满足跳出条件时，break 跳出。

while (arr[leftPointer] < pivot) { leftPointer++ }，当左指针指向的值小于基准值时，左指针不断向右移动。

while (arr[rightPointer] > pivot) { rightPointer-- }，当右指针指向的值大于基准值时，右指针不断向左移动。

if (leftPointer >= rightPointer) { break }，此时左右指针均停止移动，当左指针遇到或超过右指针时，跳出 while 循环。

else { [arr[leftPointer], arr[rightPointer]] = [arr[rightPointer], arr[leftPointer]] leftPointer++ }，此时左右指针均停止移动，当左指针未遇到或超过右指针，交换左右指针指向的元素，并重新移动左指针。

[arr[pivotIndex], arr[leftPointer]] = [arr[leftPointer], arr[pivotIndex]]，跳出 while 循环后，交换基准值和左指针指向的元素

return leftPointer，返回左指针，此时左指针指向基准值，用于为排序函数提供分隔子数组的位置。

排序

完成代码如下：

function quickSort(arr, leftPointer, rightPointer) {
  leftPointer = leftPointer ?? 0
  rightPointer = rightPointer?? arr.length - 1
  if (leftPointer >= rightPointer) return
  const pivotIndex = partition(arr, leftPointer, rightPointer)
  quickSort(arr, leftPointer, pivotIndex - 1)
  quickSort(arr, pivotIndex + 1, rightPointer)
  return arr
}

代码解读

我们来逐行解读一下：

leftPointer = leftPointer ?? 0; rightPointer = rightPointer?? arr.length - 1，设置左、右指针默认值，若 quickSort 未接收到左右指针参数，则将其置为数组的首、尾元素索引。

if (leftPointer >= rightPointer) return;，若左侧指针大于等于右侧指针，表示当前子数组内没有或只有一个元素，结束递归。

const pivotIndex = partition(arr, leftPointer, rightPointer)，调用分区函数，获取本次分区的基准值索引。

quickSort(arr, leftPointer, pivotIndex - 1)，递归处理基准值左侧的子数组，完成左侧子数组元素的排序。

quickSort(arr, pivotIndex + 1, rightPointer)，递归处理基准值右侧的子数组，完成右侧子数组元素的排序。

return arr，排序完成，返回结果。

效率解读

时间复杂度 O(NlogN)。

结语

本文重点介绍了常见排序算法的设计过程及实现，主要包括冒泡排序、选择排序、插入排序和快速排序，其中快速排序是很多编程语言内置排序函数的实现算法，很有研究意义，后续会继续更新更多的排序算法及效率解读部分。希望对您有所帮助！相关代码已上传至 GitHub，欢迎 star。

如您对文章内容有任何疑问或想深入讨论，欢迎评论区留下您的问题和见解。

技术简而不凡，创新生生不息。我是 嘟老板，咱们下期再会。

往期干货