冒泡排序是一种排序算法，你可以用它来将一组值按升序排列。如果你愿意，你也可以实现冒泡排序，以降序排序。

一个现实世界中的冒泡排序算法的例子是你手机上的联系人列表是如何按字母顺序排序的，或者根据文件的添加时间对你手机上的文件进行排序。

在这篇文章中，我将用我准备的一些信息图表解释所有你需要知道的冒泡排序算法知识。然后，我将向你展示 Python、Java 和 C++ 中的冒泡排序算法的示例代码。

目录

• 冒泡排序算法如何运行
• 排序的第一次迭代
• 排序的第二次迭代和其余部分
• 冒泡排序算法的 Python 代码示例
• 冒泡排序算法的 Java 代码示例
• 冒泡排序算法 C++ 代码实例
• 最后的思考

冒泡排序算法如何运行

为了实现冒泡排序算法，开发人员通常会写一个函数，然后在一个循环中写一个循环——内循环和外循环。当我向你展示 Python、C++ 和 Java 中的代码时，你会看到它的实际效果。

假设我们想对一系列数字 5、3、4、1 和 2 进行排序，使它们按升序排列......

排序开始的第一次迭代是比较前两个值。如果第一个值大于第二个值，算法就把第一个值推到第二个值的索引上。

排序的第一次迭代

第 1 步：在 5、3、4、1 和 2 的情况下，5 大于 3。所以 5 占用了 3 的位置，数字变成了 3、5、4、1 和 2。

第 2 步：算法现在有 3、5、4、1 和 2 需要比较，这一次，它比较了下两个值，即 5 和 4。5 比 4 大，所以 5 占用了 4 的索引，现在的值是 3、4、5、1 和 2。

第 3 步：算法现在有 3、4、5、1 和 2 需要比较。它比较下两个值，即 5 和 1。5 比 1大，所以 5 占用了 1 的索引，数字变成 3、4、1、5 和 2。

第 4 步：该算法现在有 3、4、1、5 和 2 需要比较。它比较下两个值，即 5 和 2。5 比 2 大，所以 5 占用了 2 的索引，数字变成 3、4、1、2 和 5。

这就是第一次迭代。现在数字从最初的 5、3、4、1 和 2 被排列成 3、4、1、2 和 5。正如你可能意识到的，如果数字按升序排列，5 应该是最后一个数字。这意味着第一次迭代真的完成了。

第二次迭代的排序和其余部分

该算法以 3、4、1、2、5 的最后结果开始第二次迭代。这一次，3 比 4 小，所以没有发生交换。这意味着这些数字将保持不变。

算法继续比较 4 和 1。4 比 1 大，所以 4 被换成 1，数字变成 3、1、4、2 和 5。

该算法现在开始比较 4 和 2。4 比 2 大，所以 4 被换成了 2，数字变成了 3、1、2、4 和 5。

4 现在在正确的位置，所以 4 和 5 之间没有发生互换，因为 4 比 5 小。

就这样，算法继续比较数字，直到它们按照 1、2、3、4、5 的升序排列。

冒泡排序算法的 Python 代码示例

下面是一个代码例子，展示了 Python 中冒泡排序算法的实现：

def bubble_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        flag = 0
        for j in range(0, arr_len-i-1):
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                if flag == 0:
                    break
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))

# 输出：用冒泡排序法对列表进行升序排序：[1, 2, 3, 4, 5]

要使排序以降序出现，只需将大于符号（>）替换为小于（<）。

def bubble_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        flag = 0
        for j in range(0, arr_len-i-1):
            if arr[j] < arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                if flag == 0:
                    break
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in descending order: ", bubble_sort(arr))

# 输出：用冒泡排序法对列表进行升序排序：[5, 4, 3, 2, 1]

在以下代码中，我在其中添加了注释，以便你可以知道发生了什么：

# 定义一个函数来创建排序，并传入一个数组作为参数
def bubble_sort(arr):
    # 获取数组的长度
    arr_len = len(arr)
    # 遍历数组中的元素，包括最后一个元素 - 外循环
    for i in range(arr_len-1):
        # 声明一个标志变量来检查是否发生了交换 - 用于优化
        flag = 0
        # 创建一个循环，比较数组中的每个元素，直到最后一个。
        for j in range(0, arr_len-i-1):
            # 比较两个相邻的元素，并按升序排序
            if arr[j] > arr[j+1]:
                # 如果元素的顺序不对，就交换它们
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                # 在 0 处跳出循环
                if flag == 0:
                    break
    # 返回值必须在外循环块中
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))

# 输出：用冒泡排序法对列表进行升序排序：[1, 2, 3, 4, 5]

冒泡排序算法的 Java 代码示例

要在 Java 中实现冒泡排序算法，你必须比在 Python 中写更多的代码。

这就是为什么我添加了注释，让你在执行的过程中了解这些步骤：

import java.util.Arrays;

class Main {
  static void bubbleSort(int array[]) {
    int size = array.length;
    // 遍历数组中的每个元素以读取它们
    for (int i = 0; i < size - 1; i++)
      // 用一个循环比较数组的元素
      for (int j = 0; j < size - i - 1; j++)
        // 比较数组中的两个相邻元素
        if (array[j] > array[j + 1]) {
          // 如果元素不在正确的位置，就交换它们
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  public static void main(String args[]) {
    int[] data = { 5, 3, 4, 1, 2 };
    // 用 class 名调用方法
    Main.bubbleSort(data);
    
    System.out.println("Array sorted with bubble sort: ");
    System.out.println(Arrays.toString(data));
  }
}

// 输出：用冒泡排序法对数组进行排序： [1, 2, 3, 4, 5]

冒泡排序算法 C++ 代码实例

就像我对 Java 代码所做的那样，我也为 C++ 中的冒泡排序算法的实现添加了注释，因为它比 Python 和 Java 的算法更加冗长：

#include <iostream>

using namespace std;

// 创建一个函数来执行冒泡排序
void bubble_sort(int array[], int size) {
  // 遍历数组中的每个元素以读取它们 - 外循环
  for (int step = 0; step < (size-1); ++step) {
    // 检查是否发生互换
    int swapped = 0;
    // 遍历数组中的每个元素以比较它们 - 外循环
    for (int i = 0; i < (size-step-1); ++i) {
     // 比较两个相邻的元素，并按升序排序
      if (array[i] > array[i + 1]) {

        // 如果元素的顺序不对，就交换它们
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }

    // 如果不再有交换发生，则跳出循环
    if (swapped == 0)
      break;
  }
}

// 打印一个数组
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

int main() {
  int data[] = {5, 3, 4, 1, 2};
  // find the length of the array
  int size = sizeof(data) / sizeof(data[0]);

  // 调用函数
  bubble_sort(data, size);
  
  cout << "Array sorted with bubble sort: \n";
  printArray(data, size);
}

// 输出：用冒泡排序法对数组进行排序：1  2  3  4  5

最后的思考

我不会说冒泡排序算法的实现是简单或困难的。对于一个有经验的程序员来说，这并不难，但初学者一开始可能会被吓到。

然而，要真正理解该算法的原理，你需要知道：

• 你需要写一个函数将数据[或数组]传入
• 你需要写一个外循环来访问这些元素
• 你需要写一个内循环来比较这些元素
• 你需要调用该函数并传入数据（数组）

我希望这篇文章能帮助你理解冒泡排序算法以及如何实现它。

谢谢你阅读本文。

双人回合制游戏是指两个玩家对弈，多个回合，直到其中一人获胜。这类游戏的例子有井字游戏、西洋双陆棋、曼卡拉、国际象棋和 Connect 4 四子棋。

在本教程中，我们将学习 Minimax 算法。它是一种用于决策和博弈论的回溯算法。它为棋手找到最优棋步，假设他们的对手也以最优方式下棋。它被广泛用于双人回合制游戏中。

你将学会如何创建自己的人工智能，玩上述任何游戏或其他类似游戏。另外，为了尽可能使其容易理解，我将把该算法应用于 Tic-Tac-Toe 井字游戏。

我们将不涉及创建游戏的整个过程，而只涉及与人工智能有关的部分，因为这是我们的主题。如果你对游戏创建过程感兴趣，你可以在 GitHub 上查看这个使用人工智能的井字游戏及其源代码。这是我很久以前做的一个项目，它仍然是我的最爱之一。

目录

• Minimax 算法是如何运行的
• Minimax 算法的局限性
• 如何提高该算法的时间复杂度
• 井字游戏 AI 代码
• 总结

Minimax 算法是如何运行的

Minimax 算法的方法非常简单。首先，它从一个给定的位置检查所有可能的组合。然后，假设双方都发挥得很好，它就会选择使获胜机会最大化的最佳棋步。

为了说明这一点，让我们考虑一个井字游戏，使之更有说服力。正如你可能知道的，在这个游戏中，有 2 个玩家和 9 个空位。所以我们可以用一个长度为 9 的数组来表示一个游戏。

现在让我们以这个棋盘为例：正如你所看到的，一个游戏棋盘是一个长度为 9 的数组，其值可以是 X、O 或空字符串。一个空字符串意味着这个位置仍然可用。

现在轮到 X 了。Minimax 算法将从这个位置开始尝试所有的游戏组合。然后，它将从所产生的子位置尝试所有的游戏组合，直到达到一个位置，游戏结束时，要么是 X 赢，要么是 O 赢，要么是平局（当棋盘满了，没有人赢）。

这张图说明了这是如何运行的：

我们可以使用递归来实现这一点。我将在最后展示代码，但现在，让我们专注于理解如何处理游戏组合以获得最佳棋步。我们将考虑这些情况：

• 棋盘上有一个 X 的获胜位置，等于 1 分
• 棋盘上有一个 O 的获胜位置，等于 -1 分
• 棋盘上有一个平局的位置，等于 0 分

如果我们要为 X 找到最佳棋步，我们应该找到分数最多的棋盘。但是如果一个棋盘还没有完成呢？那么我们应该根据它的子棋盘来选择棋盘——但我们该选择哪一个呢？

我需要你专注于这部分，因为这是最重要的部分。当我介绍这个算法时，我说它能找到所有的游戏组合，假设双方都在采取最优的棋步。

在第一代子棋盘之后，就会轮到 O 了。假设 O 是在采取最优棋步，我们应该选择一个 O 做得最好的棋盘，也就是分数最少的棋盘之一（因为当 O 赢的时候，该棋盘会返回 -1）。

为什么我们要这样选择呢？想象一下，如果我们在轮到 O 的时候选择最大值，那么我们就会让 X 获胜。这使得该算法毫无用处，因为我们需要假设 O 以最佳棋步下棋。

对于第三代，玩家又是 X，我们将再一次选择点数最多的棋盘。

这种交替选择最大值和最小值的方法就是这个算法被称为极小化极大值算法的原因。请看这个可视化图，以进一步了解：

这与上面的例子相同。底部的 2 个棋盘对 X 来说是赢的，所以每个棋盘都会返回 1。这里，轮到 X 了，所以我们会选择最佳值——恰好这两个棋盘的值都是 1。

正如我之前所说，如果一个棋盘不满足获胜或平局条件，我们将查看其子棋盘。这就是为什么数值为 1 的棋盘的父棋盘会有 1 的数值。

这里轮到 O，所以我们将选择可能的最低值，恰好是 1。我选择这个特定的例子是为了让事情变得简单，但这在所有棋盘上都适用。

最后又轮到了 X，我们将最大化所选棋盘的值。这就是为什么我们可以选择左边的子棋盘或右边的子棋盘或中间的子棋盘——这并不重要，因为它们的值是一样的。

最后，X 的最佳棋步是在第 7、8 或 9 位，以最大限度地提高其获胜的机会。如果你仍然不相信，可以取任何棋盘组合并画出组合树，你会得到一个满意的结果——我强烈建议在纸上画出来。

Minimax 算法的局限性

正如你所看到的，该算法是递归的，执行次数可能会变得很大。

例如，对于井字游戏，执行次数大约为 “9！”（9 的阶乘）。原因是第一步棋有 9 种可能性，然后每一步棋有 8 种可能性，以此类推。

这对井字棋来说不是问题，但考虑一下国际象棋游戏。如果我们要写出组合的数量，整个宇宙都不够用了。所以，最小值经常被用作引擎的一部分，但它不足以满足我们的需要。

如何提高算法的时间复杂度

你可能已经注意到，使用这种方法可能会导致一些重复的棋盘，我们需要多次计算它们的值。那么，为什么不在计算时存储每个棋盘的值呢？

所以现在，对于每一次迭代，我们将检查一个位置是否已经发生过。如果是的话，我们将使用它的存储值。否则，我们可以计算出位置的值，然后将其存储。

对于存储值，我们将使用一个字典，允许在 O(1) 中进行搜索。使用这种方法，我们可以降低时间复杂度——但在某些情况下，它仍然是无效的。

我曾经用这种算法做了一个四子棋游戏，它的运行时间很糟糕。因此，我没有寻找所有的组合，而是在一定的深度上停下来，这生成了一个可以提前看到 n 步的 AI。

如果你有兴趣，可以看看这个 GitHub 仓库里的四子游戏代码。我是很久以前写的，但仍然值得一看。

井字游戏 AI 代码

现在我们先来实现一些辅助函数。我们将首先检查棋盘数组中是否有 3 个水平、垂直或对角线的非空字符串值。

// 棋盘数组
let xo=['','','',
        '','','',
        '','','']

// 编写这个函数时，我们需要确保相等的值不是空字符串

// 在这之前，我将写一个辅助函数来确保 3 个索引没有空字符串

function helper(index1,index2,index3){
  return xo[index1] !='' && xo[index2] !='' && xo[index3]!=''
}



function checkwin(){
  
   return (xo[0]==xo[1] && xo[1] ==xo[2] && helper(0,1,2)) ||
          (xo[3]==xo[4] && xo[4] ==xo[5] && helper(3,4,5)) ||
          (xo[6]==xo[7] && xo[7] ==xo[8] && helper(6,7,8)) ||
          (xo[0]==xo[3] && xo[3] ==xo[6] && helper(0,3,6)) ||
          (xo[1]==xo[4] && xo[4] ==xo[7] && helper(1,4,7)) || 
          (xo[2]==xo[5] && xo[5] ==xo[8] && helper(2,5,8)) ||
          (xo[0]==xo[4] && xo[4] ==xo[8] && helper(0,4,8)) ||
          (xo[2]==xo[4] && xo[4] ==xo[6] && helper(2,4,6))
   
}

// 最后是一个检查是否有平局的函数，它将检查所有的棋盘值是否为空字符串。这个函数只有在首先检查了没有获胜条件之后才会起作用。

function boardfull(){
  return xo.every((elem)=>{
   return elem !=''
  })
}

现在我们有了检查是否存在获胜状态的函数，我们最终可以像这样写出 Minimax（我在代码中添加了注释以帮助解释）。

// 正如我之前所说的，算法将通过 board 和 ismax 参数来检查我们是否要最大化或最小化某一个回合

function minimax(board,depth,ismax){
    
    // 这是一个递归函数，所以我们应该首先设置基本情况，这将是获得平局、胜利或达到深度。
    
    // 正如你在可视化中所看到的，当出现平局或获胜条件时，不会再产生子棋盘。因此，如果在轮到 X 的时候发生了获胜的条件。赢的是 X，这就是我返回 1 的原因，同样的逻辑也适用于 Y 赢时，我在最小化时返回 -1。
    
    if (checkwin()) return ismax ? 1 : -1
    if (boardfull()) return 0
      
    if(ismax){
        
        // 当我们进行最大化时，我们将设置一个计数器为 -Infinity，只要我们遇到一个高于计数器的棋盘值，我们就将其视为最佳棋步。
        
     let best=-Infinity
     board.forEach((elem,index)=>{
         
         // 现在，为了检查所有产生的位置，我们将在棋盘上进行迭代，只要有一个可用的，我们就将其设置为 X，并在这个位置上运行 minimax。
         
     if(elem ==''){
       board[index]='X'
       let  localscores=minimax(test,depth+1,false)
       
       // 我在这里把棋盘重新设置到相同的位置
       
       board[index]=''
       best=max(best,localscores)
     }})
     return best
     }
    
 // 这里的 else 意味着我们正在最小化
    
 else{
 
     // 在这里，我们将设置我们的计数器为 + Infinity，因为我们想找到可能的最低值
     
    let best=Infinity
    board.forEach((elem,index)=>{
    if(elem ==''){
     board[index]=humanicon
     let localscores=minimax(test,depth+1,true)
     board[index]=''
     best=min(best,localscores)
    }})
    return best
  }
}

我们完成了！

总结

在这篇文章中，我们了解了 Minimax 算法、它的机制、它的局限性，以及如何改进它。现在你可以去定制 Minimax 算法，使其在各种游戏中运行，创造一些很酷的游戏机器人。

最后，我希望你从这篇文章中学到一些新东西。

如果你觉得这篇文章很有用，并想获得更多精彩的内容，请在 LinkedIn 上关注我。这将会有很大的帮助。

我挣扎了数小时，看了各种各样的教学资料、视频，敲自己脑袋，试图使用人工智能（Artificial Intelligence）创建一个无法被击败的井字棋游戏。如果你也有同样的经历，我想给你介绍极小化极大算法（Minimax algorithm）。

这种算法就像一个专业的象棋选手，总能多想几步，并且站在对手的立场来思考棋局。算法不断向前预测，直到触达棋局的最终棋子排列局面（最终状态），这一状态要么就是平局、胜利或者失败。一旦进入到最终状态，AI就会分配正分（+10）给胜利，负分（-10）给失败或者中性分（0）给平局。

同时，这个算法当轮到玩家下棋的时候，算法会评估玩家触达最终状态的步骤。当轮到AI的时候，算法会选择最大分数值的步骤，而当轮到玩家的时候，算法会选择最小分数值的步骤。极小化极大算法通过这个策略来避免AI输给玩家。

你可以使用Chrome浏览器自行测试这个游戏。

极小化极大算法可以被定义为一个递归函数，这个递归函数完成以下事情：

1. 如果到达最终状态（+10, 0, -10）返回一个值
2. 遍历棋盘所有可以落子的空位
3. 在每一个空位调用极小化极大函数（递归调用）
4. 评估调用函数的返回值
5. 返回最佳值

如果你不太熟悉递归的概念， 推荐你观看来自哈佛的CS50这个课程的视频。

让我们通过代码示例来理解极小化极大算法，在接下来的两节你会看到具体的代码以及代码的实现步骤。

极小化极大算法的代码

在这篇教程中，我们将从如图所示的接近棋局尾声开始讲解。因为极小化极大算法评估了棋局的每一个状态（非常多），所以从尾声开始能够帮助你更容易地理解极小化极大的递归调用是如何运作的。

在下图中，X代表AI，O代表的是玩家。

为了更好地处理井字棋棋盘，我们可以把它定义为一个包含9个元素的数组。每一个元素的索引（index）为它的值，这个之后会派上用场。因为图上的棋盘已经下好了X和O，所以棋盘对应的数组（origBoard）如下：

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

然后声明 aiPlayer 和 huPlayer 两个变量并分别赋值为“X”和“O”。

接下来，你需要创建寻找获胜的元素组合的函数，并在找到后返回true；还需要一个函数列举所有棋盘空位对应的索引。

/* 原始棋盘
 O |   | X
 ---------
 X |   | X
 ---------
   | O | O
 */
var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”];

// 玩家
var huPlayer = “O”;

// ai
var aiPlayer = “X”;

// 返回由棋盘所有空位的索引组成的数组
function emptyIndexies(board){
  return  board.filter(s => s != "O" && s != "X");
}

// 获胜元素组合
function winning(board, player){
 if (
 (board[0] == player && board[1] == player && board[2] == player) ||
 (board[3] == player && board[4] == player && board[5] == player) ||
 (board[6] == player && board[7] == player && board[8] == player) ||
 (board[0] == player && board[3] == player && board[6] == player) ||
 (board[1] == player && board[4] == player && board[7] == player) ||
 (board[2] == player && board[5] == player && board[8] == player) ||
 (board[0] == player && board[4] == player && board[8] == player) ||
 (board[2] == player && board[4] == player && board[6] == player)
 ) {
 return true;
 } else {
 return false;
 }
}

让我们现在进入精华部分，定义极小化极大函数（Minimax）。该函数包含 newBoard 和 player 两个参数。然后，你需要找到棋盘空位的索引，并赋值给一个变量 availSpots。

// minimax函数
function minimax(newBoard, player){
  
    //棋盘空位
    var availSpots = emptyIndexies(newBoard);

同时，你需要检查最终状态，并且返回对应的值。如果O获胜，则返回-10；如果X获胜，则返回+10。另外，如果 availSpots 数组的长度为0，则没有可以落子的空位，就是平局，返回0。

  // 检查最终状态是获胜、失败还是平局
  //并返回对应的值
  if (winning(newBoard, huPlayer)){
     return {score:-10};
  }
	else if (winning(newBoard, aiPlayer)){
    return {score:10};
	}
  else if (availSpots.length === 0){
  	return {score:0};
  }

然后，从每一个空位中收集到分数，之后再评估。因此，我们需要创建一个数组名为 moves ，并且遍历所有的空位同时收集每一步的索引和分数并存储在对象 move 中。

然后，将作为数字存储在 origBoard 的空位的索引号设置为 move 对象的索引属性。 然后，将空位设置为当前玩家的 newboard 并用对手作为参数调用 minimax 函数和修改后的 newboard。然后，存储通过调用 minimax 函数得到对象，包含 move 对象的 score 属性。

如果极小化极大函数没有到最终状态，就会递归地一层一层深入棋局游戏。直到到达最终状态，并且向上一层返回一个分数，递归才会停止。

最后，极小化极大函数重置 newBoard 为最开始的样子， 将 move 对象推入 moves 数组。

// 收集所有空位对象的数组
  var moves = [];

  // 遍历所有空位
  for (var i = 0; i < availSpots.length; i++){
    //为每一空位创建一个对象，并且存储空位索引
    var move = {};
  	move.index = newBoard[availSpots[i]];

    // 将空位设置为当前玩家
    newBoard[availSpots[i]] = player;

    //收集以对手为参数调用minimax函数的分数结果
    if (player == aiPlayer){
      var result = minimax(newBoard, huPlayer);
      move.score = result.score;
    }
    else{
      var result = minimax(newBoard, aiPlayer);
      move.score = result.score;
    }

    // 将空位重置为空
    newBoard[availSpots[i]] = move.index;

    // 将对象推入数组
    moves.push(move);
  }

然后。极小化极大算法需要在 moves 数组中搜寻最佳 move。当是AI下棋时，应该选择分数最高的 move，而当是玩家的时候，应该选择分数最低的 move。因此，如果 player 是 aiPlayer，将变量 bestScore 设置为一个非常低的数值，然后遍历整个 moves 数组， 如果 move 的 score 比 bestScore 高，算法就存储这个 move。如果发生了出现分数相同的情况，只存储第一个值。

当 player 是 huPlayer 时，也进行同样的步骤，只是 bestScore 会先被定义为一个非常大的数值，极小化极大算法再寻找最低的值存储。

最终，Minimax会返回一个存储 bestMove 的对象。

// 如果轮到AI，就遍历所有步骤，并找到分数最高的步
  var bestMove;
  if(player === aiPlayer){
    var bestScore = -10000;
    for(var i = 0; i < moves.length; i++){
      if(moves[i].score > bestScore){
        bestScore = moves[i].score;
        bestMove = i;
      }
    }
  }else{

// 如果是轮到玩家，就寻找最低的分数
    var bestScore = 10000;
    for(var i = 0; i < moves.length; i++){
      if(moves[i].score < bestScore){
        bestScore = moves[i].score;
        bestMove = i;
      }
    }
  }

// 从moves数组返回挑选出来的move（对象）
  return moves[bestMove];
}

这就是minimax函数的全部内容:) 你可以在GitHub和codepen找到算法的代码。尝试不同的棋盘，并且在控制台查看结果。

在接下来的章节，我们将通过图2所示的棋盘，来逐条查看代码，了解minimax函数到底是如何运作的。

Minimax的运行

让我们使用下面的数据，来一步一步查看的算法函数（以下简称FC）是怎么运作的。

注意：在图三中的大数字代表了每一个函数的调用，level（层级）代表游戏开始后算法向前预测了第几步。

1. origBoard 和 aiPlayer 带入算法。算法创建由找到的三个空位组成列表，从第一个空位开始遍历所有空位，检查最终状态。然后，将 aiPlayer 放入第一个空位改变 newBoard。然后用 newBoard 和 huPlayer 调用自身，等待FC返回值。

2. 当第一个FC还在运行的时候，第二个FC创建由找到的两个空位组成的列表，从第一个空格开始遍历所有空格，检查最终状态。然后，将 huPlayer 放入第一个空位改变 newBoard。然后用 newBoard 和 aiPlayer 调用自身，等待FC返回值。

3. 最后，算法会创建一个空位的列表，并且在检查最终状态后，判定玩家获胜。这样，返回一个分数（score）属性值为-10的对象。

在第二个FC中列表有两个空位， 算法将 huPlayer 带入以改变 newBoard 。然后用 newBoard 和 aiPlayer 重新调用自己。

4. 算法创建一个空位列表，然后在检查最终状态时，发现玩家获胜，因此，返回一个分数属性值为-10的对象。

在第二个FC中，算法收集了下一层的值（第三个和第四个FC的返回值）。因为轮到 huPlayer 所以要选择两个值中较小的一个。两个结果相同，所以算法选择第一个返回到上一层FC。

此时，第一个FC已经评估了将 aiPlayer 放在第一个空位的分数情况。 然后调整 newBoard，把 aiPlayer 放在第二个空位。然后用 newBoard 和 huPlayer 调用自己。

5. 到第五个FC，算法生成一个空位列表，并且在检查最终状态后发现AI获胜，因此返回一个对象，分数属性值为+10。

然后，第一个FC继续改变 newBoard，将 aiPlayer 放入第三个空格。 然后用 newBoard 和 huPlayer 调用自己。

6. 第六个FC首先创建一个有两个空位的列表， 然后修改 newBoard，把 huPlayer 放在第一个空位。然后使用 newBoard 和 aiPlayer 调用自己，并等到返回一个分数。

7. 现在算法已经有两层递归。创建一个只有一个空位的列表，然后检查最终状态。修改 newBoard，将 aiPlayer 放入空位。之后使用 newBoard 和 huPlayer 调用自己，然后等待FC返回一个可以被评估的分数。

8. 到第八个FC，算法创建空位列表，检查最终状态后发现 aiPlayer 获胜，因此，返回包含分数属性的对象，值为+10，并向上传递（第7个FC）。

第7个FC仅接受下面一层（第8个FC）的一个正值。因为当轮到 aiPlayer 时，仅得到的这个值，算法需要返回在最底层里得到的最大值。所以，仅返回一个正值（+10）到上一层（第六个FC）。

因为第6个FC有两个空位，算法修改 newBoard 把 huPlayer 放入第二个空位。然后用 newBoard 和 aiPlayer 调用自己。

9. 然后算法创建一个空格列表，检查最终状态后，发现 aiPlayer 获胜。 因此返回一个对象，分数属性为+10。

此时， 第六个FC需要从第7个FC的分数（+10）（一开始从第8个FC传上来的）和第9个FC的分数(-10)间选择。因为是轮到 huPlayer，算法使用（-10）并向上继续传递。

最终，三个分支的分数都被评估了（-10, +10, -10）。因为是aiPlayer的轮数，算法返回最大的值（+10）和这个值的索引号（4）。

在上述场景中，Minimax总结出来将X放置在棋盘中间会是最优解。:)

总结

现在你应该了解了极小化极大值算法背后的逻辑。你可以尝试使用这个算法来自己执行一遍，或者在GitHub和CodePen找到代码示例，并且优化。

感谢阅读！如果你喜欢这篇文章，希望你转发到社交媒体上。

特别鸣谢Tuba Yilmaz、Rick McGavin和Javid Askerov 对本文的审稿。

大家好！在这篇文章中，我们将研究算法，这是计算机科学和软件开发的一个关键话题。

算法是一个花哨的词，有时令人生畏，而且经常被误解。算法听起来像是一件非常困难和复杂的事情，但实际上它只不过是为了实现某个目标而必须采取的一系列步骤。

我认为关于算法的基本知识主要包括两点：

• 渐进符号（用来比较两种算法之间的性能）
• 常见任务涉及的经典算法的基本知识，如：搜索、排序和遍历

这篇文章的内容差不多就是这些。😉

让我们开始吧！

目录

• 什么是算法？
• 算法复杂度
• 查找算法
  • 线性查找
  • 二分查找
• 排序算法
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 快速排序
  • 基数排序
• 遍历算法
  • 广度优先(BFS)
  • 深度优先(DFS)
    • 先序DFS
    • 后序DFS
    • 中序DFS
• 总结

什么是算法

如前所述，算法只是为了实现某个目标而需要采取的一系列步骤。

我发现当人们第一次听到算法这个词时，他们会想象出这样的情景：

但实际上以下图片更加准确：

算法就像一本菜谱，它会指出实现目标所需遵循的必要步骤。

制作面包的菜谱如下：

1- Mix flower, salt, water and yeast //混合面粉、盐和酵母
2- Let the dough rise //发面
3- Put in the oven for 30' //在烤箱里烤30分钟
4- Let chill and enjoy //放松享受面包

题外话：希望你既能从这篇免费教程中学会如何编写代码，也能学会如何烤面包。😜

识别单词是否为“回文”（palindrome）的算法可以写成：

function isPalindrome(word) {
	// 第一步：在单词的两端分别放置两个指针
    // 第二步：指针向字符串中心方向遍历
	// 第三步：每一次遍历都检查两个指针所在位置的值是否一致
	// 一旦不满足这个条件，该单词就不是回文
    let left = 0
    let right = word.length-1

    while (left < right) {
        if (word[left] !== word[right]) return false
        left++
        right--
    }
    
    return true
}

isPalindrome("neuquen") // true
isPalindrome("Buenos Aires") // false

这个算法就和菜谱类似，设定一个目标，并将目标拆分成不同步骤，这些步骤以给定的顺序执行，以达到我们想要的结果。

维基百科对算法的定义如下：

算法是明确定义的一连串有序的指令，通常用于解决一类特定问题或者执行计算。

算法复杂度

现在我们知道了什么是算法，让我们来学习如何比较不同的算法。

假设我们遇到下面的问题：

写一个函数，这个函数包含两个参数：一个是非空数组，这个数组中的元素是不重复的整数；另一个是一个整数，值为目标总和。如果数组中任意两个整数加起来等于目标整数，函数返回包含这两个整数的数组，如果没有任何两个数的总和是目标整数，函数返回空数组。

以下是一种解法：

function twoNumberSum(array, targetSum) {
    let result = []
    // 我们使用嵌套循环来测试数组中每一个可能的数字组合
        for (let i = 0; i < array.length; i++) {
          for (let j = i+1; j < array.length; j++) {
              // 如果我们找到合适的组合，就把值推入结果数组，并返回
              if (array[i] + array[j] === targetSum) {
                  result.push(array[i])
                  result.push(array[j])
                  return result
              }
          }
      }
      // 返回结果数组
      return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

以下是另一个种解法：

function twoNumberSum(array, targetSum) {
	// 从小到大排列数组，并在两个边界分别放一个指针，向数组中间方向遍历
	// 每一次遍历都查看两个指针所在位置的值之和是否等于目标值
	// 如果大于目标值，将右指针向左移
	// 如果小于目标值，将左指针向右移
	let sortedArray = array.sort((a,b) => a-b)
	let leftLimit = 0
	let rightLimit = sortedArray.length-1

	while (leftLimit < rightLimit) {
			const currentSum = sortedArray[leftLimit] + sortedArray[rightLimit]

			if (currentSum === targetSum) return [sortedArray[leftLimit], sortedArray[rightLimit]]
			else currentSum < targetSum ? leftLimit++ : rightLimit--        
	}

	return []
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

还有一种解法：

function twoNumberSum(array, targetSum) {
    // 仅遍历一次数组
    // 在每次遍历中检查指针所在当前值与目标值的差值是否存在于数组
    // 如果存在，则返回指针所在位置的值和差值
	let result = []

	for (let i = 0; i < array.length; i++) {
        let desiredNumber = targetSum - array[i]
        if (array.indexOf(desiredNumber) !== -1 && array.indexOf(desiredNumber) !== i) {
            result.push(array[i])
            result.push(array[array.indexOf(desiredNumber)])
            break
        }
	}
 
    return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

这三种都完成了目标，但我们可以对比哪一个解法更好吗？

除了有效性 （是否达成目标）以外， 我们还会根据 效率来衡量算法， 即是否在 时间上 （处理时间）和 空间上 （内存的使用）占用最少的资源。

这很容易马上想到对策——“就去测量算法运行了多长时间不就好了吗？”，这样做确实有效。

但问题是由于计算机硬件和配置的不同，同一个算法在不同的计算机上运行时长也会不同；即便是在同一个台计算机上，后台的运行任务不同也会影响算法的时长。

需要一个客观且不会发生变化的方式来计算算法的性能，渐进符号就派上用场了。

渐进符号（又称大O符号）是用来 分析和比较当输入增加时算法的性能变化的一种系统。

大O是分析和比较不同算法复杂度（时间和空间上）的一种标准方法，因为复杂度的计算的是输入发生变化时，算法运行的次数的变化，无论环境发生什么改变，两者之间的关系不变。

有各种各样复杂度的算法，但是最常用的几个如下：

• 常数 — O(1)： 指对运行次数和空间的需求永远独立于输入，保持不变的时候。比如向一个函数输入一个数字，返回这个数字减去10的结果。不论你输入的是100还是1000000，函数始终都运行单个运算（减去10），所以复杂度是常数O(1)。
• 对数 — O(log n)： 指随着输入的增加，所需的运行次数和空间需求的增长逐渐放缓。这种类型的复杂性通常出现在分治算法或查找算法中。经典的例子是二分查找，通过不断将数据集拆分成两部分，得到最终结果。
• 线性 — O(n)： 指所需的运行次数和空间需求与输入同速率增长时。以打印数组每一个值的循环为例，运行的次数会随着数组的长度而增长，所以复杂度是线性的 O(n)。
• 平方 — O(n²)： 指所需运行次数和空间需求以输入的平方增长时。嵌套循环是这个的经典例子。假设我们有一个遍历整个数字数组的循环，并且在该循环中有另一个循环再次遍历整个数组。这样数组中的每个值都被遍历了两次，因此复杂度是平方 O(n²)。

请注意在讨论时间和空间复杂度时使用相同的符号。例如，一个函数无论它接收到什么输入，它总是创建一个具有单个值的数组，那么空间复杂度将是常数 O(1)，以此类推其他复杂度类型。

为了更好地理解，让我们回到之前的问题，并分析解决方案的复杂度。

示例1：

function twoNumberSum(array, targetSum) {
    let result = []
    //  我们使用嵌套循环来测试数组中每一个可能的数字组合
        for (let i = 0; i < array.length; i++) {
          for (let j = i+1; j < array.length; j++) {
              //  如果我们找到合适的组合，就把值推入结果数组，并返回
              if (array[i] + array[j] === targetSum) {
                  result.push(array[i])
                  result.push(array[j])
                  return result
              }
          }
      }
      // 返回结果数组
      return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

在这个例子中，我们遍历参数数组，对于数组中的每个值，我们再次遍历整个数组，寻找一个和这个值加起来为目标总和的数字。

每一次遍历为一个任务：

• 如果数组中有3个数字，那么每一个数字都需要遍历三遍一共9遍（三乘以数组里的三个数字），这个任务总共要执行12次。
• 如果数组中有4个数字，那么每一个数字都需要遍历4遍一共16遍（四乘以数组里的三个数字），这个任务总共要执行20次。
• 如果数组中有5个数字，那么每一个数字都需要遍历5遍一共25遍（五乘以数组里的三个数字），这个任务总共要执行30次。

可以看到，与输入相比该算法中的任务数量如何呈指数增长且不成比例。该算法的复杂度是平方 – O(n²)。

每当我们遇到嵌套遍历，我们的反应链应该是平方复杂度 => 不妙 => 可能有更好的解决办法。

示例2：

function twoNumberSum(array, targetSum) {
    // 从小到大排列数组，并在两个边界分别放一个指针，向数组中间方向遍历
	// 每一次遍历都查看两个指针所在位置的值之和是否等于目标值
	// 如果大于目标值，将右指针向左移
	// 如果小于目标值，将左指针向右移
	let sortedArray = array.sort((a,b) => a-b)
	let leftLimit = 0
	let rightLimit = sortedArray.length-1

	while (leftLimit < rightLimit) {
			const currentSum = sortedArray[leftLimit] + sortedArray[rightLimit]

			if (currentSum === targetSum) return [sortedArray[leftLimit], sortedArray[rightLimit]]
			else currentSum < targetSum ? leftLimit++ : rightLimit--        
	}

	return []
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

在这个例子中，我们在遍历前对数组进行了排序，通过边界的两个指针向内遍历使得我们仅遍历了一次数组。

因为我们仅遍历了一次数组，所以这个解法比上个好。但是我们对数组进行了排序（通常是对数复杂度）然后再遍历（线性复杂度）。这个解法的复杂度为 O(n log(n))。

示例3：

function twoNumberSum(array, targetSum) {
    // 仅遍历一次数组
    // 在每次遍历中检查指针所在当前值与目标值的差值是否存在于数组
    // 如果存在，则返回指针所在位置的值和差值
	let result = []

	for (let i = 0; i < array.length; i++) {
        let desiredNumber = targetSum - array[i]
        if (array.indexOf(desiredNumber) !== -1 && array.indexOf(desiredNumber) !== i) {
            result.push(array[i])
            result.push(array[array.indexOf(desiredNumber)])
            break
        }
	}

    return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

在这个例子中，我们仅遍历了一次，并且在遍历之前没有做任何操作。因为了任务数量为三个里面最少的，所以这是最优解。这种情况的复杂度为 – O(n)。

复杂度就是 算法背后最重要的概念。了解如何比较不同的实现，哪一种方式更为有效十分有必要，因此如果你对这个概念尚不清晰，我鼓励你再看一遍上面的例子，或者查阅其他的资料。你还可以 观看这个超级棒的freeCodeCamp 视频教学。

查找算法

在了解了算法复杂度之后，我们来看看用于解决常见程序任务的常用算法。让我们从查找算法开始。

若想要在一个数据结构中查找一个值，可以采用不同种类的方法。我们将展开讲讲并对比两个最常见的方法。

线性查找

线性查找是通过遍历整个数据结构，每次查找一个值，看是否与目标值匹配。 这或许是最符合直觉的查找方式，如果查找是未被排序的数据结构，这是最好的方式。

假设有一个数字数组，我们需要为这个数组编写一个函数，这个函数以单个数字为输入，如果这个数字在数组内则返回这个数字的索引，如果不在，则返回-1.一个可能的解法如下：

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

const search = num => {
    for (let i = 0; i < arr.length; i++) {
        if (num === arr[i]) return i
    }
    return -1
}

console.log(search(6)) // 5
console.log(search(11)) // -1

因为数组未被排序，所以我们并不知道每个值的大概位置，最好的办法就是一次检查一个值。这种算法的复杂度是 线性- O(n)，因为最坏的情况是我们遍历了整个数组才找到我们需要的值。

线性查找被很多JavaScript内置方法采用，如 indexOf、 includes和findIndex。

二分查找

当数据是被排序过的时候，我们可以使用更有效率的办法：二分查找。二分查找的步骤如下：

• 选择数据结构的中间值后“提问”：这是我们需要的值吗？
• 如果不是，“提问”：这个值是比我们需要的值大还是小？
• 如果更大，则“丢弃”掉比中间值小的那一半数据，如果更小，则“丢弃”比中间值大的那一半数据。
• 不断重复上述操作，直找到我们需要的值，或者剩下的“部分”已经不能被平分了。

二分查找最棒的地方在于每一次遍历我们几乎都丢弃掉了一半数据。这使得查找更加快速高效。 👌

假设针对同一组数组（排过序）我们需要编写一样的函数，输入一个数字，返回这个数字在数组中的索引，或者如果数字不存在数组中，返回-1。使用二分查找的写法如下：

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

const search = num => {
    //我们将使用三个指针
    //一个位于左边界，一个位于右边界，一个位于数组的中间
    let start = 0
    let end = arr.length-1
    let middle = Math.floor((start+end)/2)

    // 当我们并没有找到目标值，并且开始值小于等于结束值的时候
    while (arr[middle] !== num && start <= end) {
        // 如果目标值比中间值要小，丢弃掉数值更大的一半数组
        if (num < arr[middle]) end = middle - 1
        // 如果目标值比中间值大，丢弃掉数值更小的一半数组
        else start = middle + 1
        // 重新计算中间值
        middle = Math.floor((start+end)/2)
    }
    // 如果找到目标值或者数组不能再被对半分的情况下，跳出循环
    return arr[middle] === num ? middle : -1
}

console.log(search(6)) // 5
console.log(search(11)) // -1

这种方法看上去写了“更多代码”，但可能发生的遍历去比线性查找要少了很多，因为我们每一次遍历都丢弃了一半的数组。这种算法的复杂度为 对数的 – O(log n)。

排序算法

我们可以采取不同的方法对数据结构排序，让我们来看看一些最常用的排序方法以及它们之间的区别。

冒泡排序

冒泡排序遍历整个数据结构，一次对比一对值。如果这对值的顺序不对，则交换位置来调整顺序，遍历一直持续到所有数据的顺序正确。这个算法将更大的值“冒泡”至数组的末尾。

因为每一个值都要和剩下的所有值做一次对比，这种算法的复杂度是 平方 – O(n²)。

以下是一种实现方式：

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

const bubbleSort = arr => {
    // 设置一个标记变量
    let noSwaps
	
    //我们需要一个嵌套循环
    // 一个从右至左遍历的指针
    for (let i = arr.length; i > 0; i--) {
        noSwaps = true
		// 和一个从右至左遍历的指针
        for (let j = 0; j < i-1; j++) {
            //比较两个指针
            if (arr[j] > arr[j+1]) {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                noSwaps = false
            }
        }
        if (noSwaps) break
    }
}

bubbleSort(arr)
console.log(arr) // [1,2,3,4,5,6,7,8,9,10]

选择排序

选择排序和冒泡排序类似，差别在于选择排序不是将更大的值放在数据结构的末尾，而是将更小的值放在数据结构的开始。具体步骤如下：

• 将数据的第一个元素存储为最小值
• 遍历整个数据结构，将每一个值与最小值做对比，如果找到比最小值更小的值，就将其设置为新的最小值
• 如果最小值不是数据结构的第一个值，则将最小值的位置与第一个值的位置交换。
• 重复上述操作直至数组排序正确

这种算法的复杂度为平方 – O(n²)。

一个可能的实现办法如下：

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

const selectionSort = arr => {
    
    for (let i = 0; i < arr.length; i++) {
        let lowest = i
        
        for (let j = i+1; j < arr.length; j++) {
            if (arr[j] < arr[lowest]) {
                lowest = j
            }
        }

        if (i !== lowest) {
            let temp = arr[i]
            arr[i] = arr[lowest]
            arr[lowest] = temp
        }
    }
}

selectionSort(arr)
console.log(arr) // [1,2,3,4,5,6,7,8,9,10]

插入排序

插入排序是创建一个“有序的一半”来对数据结构进行排序，遍历整个数据结构，将每一个元素插入到“有序一半”的正确位置。

具体步骤如下：

• 首先挑选数据结构中的第二个元素
• 将其与前一个元素进行比较，必要时进行位置交换
• 继续进入到下一个元素，如果这个元素不在正确的位置，就遍历“有序的一半”找到正确的位置，并且将这个元素插入进去
• 重复上述步骤直至数据结构顺序正确

这个算法的复杂度为平方(O(n²))。

一个可能的实现方案如下：

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

const insertionSort = arr => {
    let currentVal
    
    for (let i = 1; i < arr.length; i++) {
        currentVal = arr[i]

        for (var j = i-1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal
        
    }
    
    return arr
}

insertionSort(arr)
console.log(arr) // [1,2,3,4,5,6,7,8,9,10]

冒泡排序、选择排序和插入排序的问题在于并不好扩展。

当我们处理大数据集时，有更好的选择：其中包括归并排序、快速排序和基数排序。那么让我们现在来看看这些吧！

归并排序

归并排序是一种算法，它重复将数据结构分解为单个值，然后按照顺序地组合它。

具体步骤如下：

• 递归地将数据平分两半直至每一个“一半”仅有一个值
• 再递归地将各个“一半”排序直至合并成原数组长度的数组

这个算法的复杂度为 O(n log n)， 因为拆解数组的复杂度为log n，而对比大小的复杂度为n。

一个可能的实现方法如下：

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

// 归并函数
const merge = (arr1, arr2) => {
    const results = []
    let i = 0
    let j = 0

    while (i < arr1.length && j < arr2.length) {
        if (arr2[j] > arr1[i]) {
            results.push(arr1[i])
            i++
        } else {
            results.push(arr2[j])
            j++
        }
    }

    while (i < arr1.length) {
        results.push(arr1[i])
        i++
    }

    while (j < arr2.length) {
        results.push(arr2[j])
        j++
    }

    return results
}

const mergeSort = arr => {
    if (arr.length <= 1) return arr
    let mid = Math.floor(arr.length/2)
    let left = mergeSort(arr.slice(0,mid))
    let right = mergeSort(arr.slice(mid))
    return merge(left, right)
}

console.log(mergeSort(arr)) // [1,2,3,4,5,6,7,8,9,10]

快速排序

快速排序通过选择一个元素（称为“基准”），并最终确定基准应在在一个排好序的数组里的索引位置。

快速排序的运行时间部分取决于选择基准的方式。理想情况下，它应该是被排序后的数据集的中间值。

具体步骤如下：

• 识别基准值，并放置在应该放置的索引位置
• 递归地沿用上述方式对数据结构每一个“一半”进行操作。

这个算法的复杂度是O(n log n)。

一种可能的实现方式如下：

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

const pivot = (arr, start = 0, end = arr.length - 1) => {
    const swap = (arr, idx1, idx2) => [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]

    let pivot = arr[start]
    let swapIdx = start

    for (let i = start+1; i <= end; i++) {
        if (pivot > arr[i]) {
            swapIdx++
            swap(arr, swapIdx, i)
        }
    }

    swap(arr, start, swapIdx)
    return swapIdx
}

const quickSort = (arr, left = 0, right = arr.length - 1) => {
    if (left < right) {
        let pivotIndex = pivot(arr, left, right)
        quickSort(arr, left, pivotIndex-1)
        quickSort(arr, pivotIndex+1, right)
    }

    return arr
}

console.log(quickSort(arr)) // [1,2,3,4,5,6,7,8,9,10]

基数排序

基数算法和前面我们看到的这些算法的运行方式不太一样，因为基数算法并不对比值。基数算法根据数字位数来判断数字大小（位数越多数字越大），从而给数组进行排序。

基数算法是按照位数来给数字排序。它首先按第一个位数对所有值进行排序，然后再按第二个位数，然后按第三个位数……这个过程重复的次数与列表中最大数字的位数一样多。在这个过程结束时，算法返回完全排序后的列表。

具体步骤如下：

• 计算出最大的数字有多少位数
• 循环遍历列表直到最大位数。在每次迭代中：
• 为每个位数（从 0 到 9）创建“桶”，并根据评估将每个值放入其对应的桶中。
• 将现有列表替换为在桶中排序的值，从 0 开始到 9。

这个算法的复杂度为 O(n*k)，k是最大数的位数。因为没有相互比较大小，所以这个算法的运行速度比其他的要快，但是这个方法只对数字列表奏效。

如果想要使用一个与数据无关的排序算法，可以使用我们之前讨论的方法。

一种可能的实现方式如下：

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

const getDigit = (num, i) => Math.floor(Math.abs(num) / Math.pow(10, i)) % 10

const digitCount = num => {
    if (num === 0) return 1
    return Math.floor(Math.log10(Math.abs(num))) + 1
}

const mostDigits = nums => {
    let maxDigits = 0

    for (let i = 0; i < nums.length; i++) maxDigits = Math.max(maxDigits, digitCount(nums[i]))

    return maxDigits
}

const radixSort = nums => {
    let maxDigitCount = mostDigits(nums)

    for (let k = 0; k < maxDigitCount; k++) {
        let digitBuckets = Array.from({ length: 10 }, () => [])
        
        for (let i = 0; i < nums.length; i++) {
            let digit = getDigit(nums[i], k)
            digitBuckets[digit].push(nums[i])
        }

        nums = [].concat(...digitBuckets)
    }

    return nums
}

console.log(radixSort(arr)) // [1,2,3,4,5,6,7,8,9,10]

遍历算法

我们要讨论的最后一种算法是遍历算法，这种算法使用不同方法遍历整个数据结构（主要是树结构和图）。

当我们遍历树结构的时候，我们可以从广度和深度两个方向给数据结构进行优先级排序。

如果我们以深度优先，我们会顺着分支往下遍历整个树，从树首到每一个分支的叶子。

如果我们优先对广度进行搜索，我们就横向地遍历树的每一个节点，然后再遍历到下一个层次。

选取哪一种方式主要取决于我们要遍历的是什么以及数据结构是怎么构建的。

广度优先（BFS）

让我们首先来分析BFS。正如我们介绍过的，BFS会首先横向遍历数组。在下面的图示中，数值将以这个顺序被遍历： [10, 6, 15, 3, 8, 20].

一般来说，BFS分为以下几个步骤：

• 创建一个队列和变量来存储”被访问过“的节点
• 将根节点放置在队列
• 只要队列中有元素，就循环下去
• 将节点移出队列，并保存在存储被访问过节点的变量中
• 如果被移除的节点对象有左侧属性，则添加到队列
• 如果被移除的节点对象有右侧属性，则添加到队列

一个可行的实现方法如下：

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}

class BinarySearchTree {
    constructor(){ this.root = null; }

    insert(value){
        let newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        let current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    BFS(){
        let node = this.root,
            data = [],
            queue = [];
        queue.push(node);

        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }
}


const tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.BFS()) // [ 10, 6, 15, 3, 8, 20 ]

深度优先（DFS)

DFS会首先横向遍历数组。在上面的图示中，数值将以这个顺序被遍历:[10, 6, 3, 8, 15, 20].

这种DFS又称作“先序遍历”，DFS主要分为三种，这三种的区别在于节点被遍历的顺序。

• 先序： 先访问当前节点，然后左边的节点，然后右边的节点
• 后序： 先访问所有左手边的子节点，再访问所有右手边的子节点，最后访问当前节点
• 中序： 想访问所有左手边的节点，再访问当前节点，最后访问所有右手边节点

现在听上去可能有些让人困惑，不过没关系，看了后面的例子你就会明白了。

先序DFS

在先序DFS中，我们将进行以下步骤：

• 创建一个存储所有被访问过的节点
• 在变量中存储树的根节点
• 编写一个辅助函数接受节点作为参数
• 将节点的值推入存储值的变量中
• 如果节点对象有左属性，则将左节点作为参数调用辅助函数
• 如果节点对象有左属性，则将右节点作为参数调用辅助函数

一个可行的实现如下：

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }

}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSPreOrder()) // [ 10, 6, 3, 8, 15, 20 ]

后续DFS

后续DFS算法的执行步骤如下：

• 创建一个变量存储访问过的节点
• 在变量中存储树的根节点
• 编写一个辅助函数接受节点作为参数
• 如果节点对象有左属性，则参入左节点作为参数调用辅助函数
• 如果节点对象有右属性，则参入右节点作为参数调用辅助函数
• 用当前节点作为参数调用辅助函数

一个可行的执行如下：

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }


    DFSPostOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.value);
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSPostOrder()) // [ 3, 8, 6, 20, 15, 10 ]

中序DFS

中序DFS算法的执行步骤如下：

• 创建一个变量存储被访问过的节点
• 在变量中存储树结构的根节点
• 编写一个以节点作为参数的辅助函数
• 如果这个节点对象有左属性，将所有左节点作为参数调用辅助函数
• 将节点的值推入存储的值的变量中
• 如果这个节点对象有左属性，将所有右节点作为参数调用辅助函数
• 将当前节点作为参数调用辅助函数

一个可行的实现如：

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    DFSInOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.value);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSInOrder()) // [ 3, 6, 8, 10, 15, 20 ]

你可能已经注意到，先序、后序和中序的实现非常类似，仅改变了遍历节点的顺序。但其实这三种实现得到的结果大相径庭，有时其中一种方法可能比其他的要有用得多。

何时使用BFS或者DFS取决于数据结构是如何组织的

一般来说如果你有一个结构非常宽的树或者图（意味着在同一水平线上有很多后代节点），就应该采用深度优先。如果是处理分支很长的大型树或者图，就应该使用广度优先。

两种算法的时间复杂度是一样的，因为我们始终遍历了所有节点一次。但是空间复杂度取决于有多少节点被存储在内存中，所以不相同。因此记录越少的节点越好。

总结

希望享受阅读这篇文章，并且从中有所收获。你可以在LinkedIn或者Twitter上关注我。

下篇文章见！

您是否也曾想过：

• 如何压缩某些东西而不丢失任何数据？
• 为什么有些算法压缩得比其他算法好？
• GZIP 是如何工作？

假设我们要压缩一个字符串（霍夫曼编码可以用于任何数据，但是字符串是很好的例子）。

不可避免地，在要压缩的文本中，某些字符会比其他字符出现得更频繁。 霍夫曼编码（Huffman Coding）基于这一事实，对文本进行了编码，以使最常用的字符比不常用的字符占用更少的空间。

编码字符串

让我们使用霍夫曼编码来压缩星球大战中 Yoda 的口头禅： “do or do not”。

“do or do not” 的长度为 12 个字符。 它有几个重复的字符，因此应该可以压缩一下。

为了便于讨论，假设存储每个字符需要 8 bits（字符编码完全是另一个主题）。这句话将占用 96 bits，但是使用霍夫曼编码可以做得更好！

先从建立树形结构开始。 数据中出现频率更高的字符更靠近树的根，而离根远的节点字符出现频率更低。

这是字符串 “do or do not” 的霍夫曼树：

字符串中最常见的字符是 “ o”（出现 4 次）和空格（出现 3 次）。请注意，这些字符的路径离根只有两步，而最不常见的字符（"t"）则有三步。

所以，可以不存储字符，而存储指向字符的路径。

从根节点开始，然后沿着树一直向着要编码的字符前进。 如果向左走，则将存储一个 0，如果向右走，则将存储一个 1。

这是使用这棵树编码第一个字符 d 的方法：

最终结果是 1 0 0 - 3 位而不是 8 位。这是一个很大的改进！

编码后的全部字符串如下所示：

占用 29 位而不是 96 位，并且没有数据丢失。 优秀！

解码字符串

要解码文本，只需根据 0（左分支）或 1（右分支）前进，直到获取到一个字符。 写下该字符，然后从顶部重新开始：

发送编码后的文本

但是等等，当我们将编码后的文本发送给其他人时，他们不是也需要这个编码树？ 是的！ 另一端需要相同的霍夫曼树才能正确解码文本。

最简单也是最低效的方法是将树与压缩文本一起发送。

当然也可以先约定同一棵树，然后使用该树对字符串进行编解码。 如果可以提前预测字符的分布，构建一个相对高效而无需每次都分析内容的树（例如，使用英文文本）也是可以的。

另一种选择是发送足够多的信息，以保证另一端与我们建立的是同一棵树（这也是 GZIP 的工作方式）。 例如，我们可以发送每个字符出现的总次数。 但是必须要小心；对于相同的文本块，可能有不止一个霍夫曼树，因此必须确保双方都以完全相同的方式构造树。

想要了解更多？

查看以下链接：

• How to build the Huffman tree (it’s easier than you think)
• How this is used in GZIP

原文：What is Huffman Coding? 作者：Dave

在这篇文章里我们会使用生日蛋糕来阐述大 O 表示法时间复杂度。假设我们正在举办 party，需要基于参会的人数烘焙蛋糕。

O(1) - 常数时间

对于常数时间，不管多少人参加生日聚会，都只需要做一个蛋糕。因此制作蛋糕的时间是一个常量。

注意大 O 表示法无需指定这个常数时间是多少（制作蛋糕可能花费一个小时，也可能花费四个小时）。它只是陈述了时间不随着参会人数的增加而增加。

一个 O(1) 操作的例子是通过 index 访问数组的元素。从 10 个元素的数组检索一个元素和从 100 万个元素的数组里检索一个元素一样快。

O(log n) - 对数时间

对于对数时间，生日蛋糕用来奖励先到的人。

第一个到的人独享蛋糕，接下来到的两个人分一个蛋糕，在接着到的四个人分一个蛋糕，以此类推。

因此一个人聚会需要一个蛋糕。两人或者三人聚会需要两个蛋糕。4 - 7人聚会需要 3 个蛋糕。8 - 15 人聚会需要四个蛋糕。 ‘n’ 个人聚会需要 log_2_(n) 个蛋糕。

一个 O(log n) 操作的例子是有序数组的二分查找。

二分查找算法找到数组中间的元素，和要找的元素进行对比。因为数组是有序的，所以可以知道要找的值在数组的哪一半里面。

然后再一半的数组里面重复这一过程。对于 16 个元素的数组，第一次迭代将搜索范围缩小到 8，然后依次是 4、2、1。最多 4 次，也就是 log_2_(16) 次，迭代结束。

O(n) - 线性时间

对于线性时间，每个参会的人都有一个蛋糕。如果 ‘n’ 个人参会需要准备 ‘n’ 个蛋糕，因此花费的时间和参会的人数相关。

再一次，大 O 表示法不关注具体时间是多少（可能是一个小时制作一个蛋糕，也可能是四个小时），它只是表示时间随着参会人数线性增长。

一个 O(n) 操作的例子是用最粗暴的方式在数组里遍历找到指定元素。在 10 个元素的数组里，最坏情况下需要找十次才能找到指定元素。在 100 万个元素的数组里，可能需要找 100 万次。

当然，可能很快就能找到想要的值，但是大 O 表示法描述的是算法会花费的最大时间。

O(n^2) - 二次时间

对于二次时间，每个参会者都有自己的蛋糕，另外，每个蛋糕上的奶油都有所有人的签名。

在这种情况下一人参会需要 1 个蛋糕和 1 个签名。两人参会需要 2 个蛋糕，每个蛋糕都需要 2 个名字（一共 4 个名字）。三人参会需要 3个蛋糕，每个蛋糕都有 3 个名字，一共 9 个名字。

‘n’ 个人参会需要签 n*n 个名字（也就是 n 的平方或者 n 的二次方），因此制作蛋糕（以及签名）的时间和参会人数的平方相关。

O(n^2) 操作的一个例子是暴力搜索数组中的重复项。遍历数组中的所有元素，对于每一个元素，在遍历一遍数组看是否有和其相同的元素。

对于 10 个元素的数组，外部需要循环 10 次，每一次外部循环都需要内部循环 10 次，总共是 100 次。对于 100 万个元素的数组，需要 10000 亿次。

还有一个比 O(n^2) 更普遍的情况，和时间与 n 的平方相关不同，它与 n 的 c 次方相关 （n^c）。这通常叫做多项式时间。

O(n!) - 阶乘时间

阶乘时间，所有参会的人进行法式滚球比赛，赢的人拿走蛋糕。

还存在一个小问题，先投球的玩家会更劣势。为了解决这个问题，同时进行多场比赛，每组都会先手一次。所有比赛的排列都会写在蛋糕的奶油上。

这意味着两人参会会有两场比赛，每一个选手都会依次先手。三人参会会有 6 场比赛（假设选手为安娜 A、布莱恩 B 和克里斯 C，那么排列会是 ABC、ACB、BAC、BCA、CAB、CBA）。

‘n’ 个人参会需要 n! 或者 n 的阶乘次比赛，制作蛋糕的时间与阶乘相关。

n! 的计算是从 n 到 1 的所有数相乘， “n * (n - 1) * (n - 2) …… * 2 * 1”。对于两人聚会就是 2 * 1 也就是 2。对于三人聚会就是 3 * 2 * 1，也就是 6。

需要分析列表组合的算法就是 O(n!) 操作，比如旅行商问题。

结论

希望生日蛋糕能让大 O 表示法更好理解。下图也是一个很好的记忆辅助工具，展示了算法的相对速度（如果有的选，要选更快的算法！）

还有一些其它的大 O 表示法，比如 O(n log n) 和 O(c^n)，但是他们都遵循相同的模式，如果想了解更多，查看这篇文章。

原文：How Big O Notation Works – Explained with Cake，作者：cedd burge

你将学到：

• 图的基本概念。
• Dijkstra 算法的使用场景。
• Dijkstra 算法的工作原理。

开始吧。✨

🔹 “图”简介

基本概念

图是一种用来表示元素对之间的“连接”的数据结构。

• 这些元素称为节点，它们表示现实生活中的对象、人或实体。
• 节点之间的连接称为边。

下面是“图”的图形表示：

彩色的圆圈表示节点，圆圈之间的连线表示边。

💡 提示： 如果两个节点之间有连线表示它们是互相连接的。

应用

图可以应用到现实世界中的场景，例如：可以用来建模交通运输网络，节点表示发送或接收物资的站点，边表示站点之间的路线（如下图所示）。

用图表示交通运输网络

图的类型

图可以是：

• 无向的： 在互相连接的节点之间可以以任意方向移动。
• 有向的： 在互相连接的节点之间只能以特定的方向移动。使用带单向箭头的线来表示有向边。

💡 提示： 本文中使用的是无向图

权重图

权重图的边是带有“权重”的，边的权重可以表示距离、时间或其他能够以节点之间的“连接”表示的概念。

下面的权重图中，每个边旁边都有一个蓝色数字表示其权重。

💡 提示： 这些权重对于 Dijkstra 算法而言是必不可少的，稍后会解释其原因。

🔸 Dijkstra 算法简介

了解了图的基本概念，我们开始研究这个出色的算法。

• 算法目标和使用场景
• 历史
• 基础知识
• 必要条件

算法目标和使用场景

使用 Dijkstra 算法，可以寻找图中节点之间的最短路径。特别是，可以在图中寻找一个节点（称为“源节点”）到所有其它节点的最短路径，生成一个最短路径树。

GPS 设备使用这个算法来寻找当前位置到目标位置的最短路径。Dijkstra 算法被广泛应用在工业上，尤其是需要建模网络的领域。

历史

荷兰杰出计算机科学家、软件工程师 Dr. Edsger W. Dijkstra 创建并发布了这个算法。

1959 年，他发表了一篇 3 页的文章《A note on two problems in connexion with graphs》来介绍他的新算法。

1994 年，Edsger Dijkstra 博士 在 ETH Zurich（Andreas F. Borchert 摄）

在 2001 年的一次采访中，Dijkstra 博士透露了他设计这个算法的起因和过程：

从 Rotterdam 到 Groningen 的最短路线是什么？我花了大概 20 分钟时间设计了这个寻找最短路径的算法。一天早上我正和我年轻的未婚妻在 Amsterdam 逛街，觉得有点累了，我们就坐在咖啡厅的露台上喝了一杯咖啡，我在想是否能够解决这个问题，然后，我设计出了这个最短路径算法。我说过，这是一个 20 分钟的设计。事实上，三年之后的 1959 年它才被发布，现在看来依然很不错，其原因之一是我当时设计的时候没有纸和笔，从而不得不极力避免所有可避免的复杂性。最终，令我惊讶的是，这个算法成为了我成名的基石之一。——引自文章《An interview with Edsger W. Dijkstra》.

⭐ 难以置信，对吧？ 仅仅 20 分钟的时间，Dijkstra 博士设计出了位列计算机科学史上最著名的算法之一的 Dijkstra 算法。

Dijkstra 算法的基础知识

• Dijkstra 算法从指定的节点（源节点）出发，寻找它与图中所有其它节点之间的最短路径。
• Dijkstra 算法会记录当前已知的最短路径，并在寻找到更短的路径时更新。
• 一旦找到源节点与其他节点之间的最短路径，那个节点会被标记为“已访问”并添加到路径中。
• 重复寻找过程，直到图中所有节点都已经添加到路径中。这样，就可以得到从源节点出发访问所有其他节点的最短路径方案。

必要条件

Dijkstra 只能用在权重为正的图中，因为计算过程中需要将边的权重相加来寻找最短路径。

如果图中有负权重的边，这个算法就无法正常工作。一旦一个节点被标记为“已访问”，当前访问它的路径就被标记为访问它的最短路径。如果存在负权重，则可能在之后的计算中得到总权重更小的路径，从而影响之前的结果（译注：即可能出现多绕路反而路线更短的情况，不合实际）。

🔹 Dijkstra 算法示例

理解了算法概念之后，通过逐步的示例来了解一下它背后的工作原理。

假设有下面这个图：

Dijkstra 算法将会寻找出图中节点 0 到所有其他节点的最短路径。

💡 提示： 在这个图中，我们假定两个节点之间的权重表示它们之间的距离。

我们将会得到节点 0 到节点 1、节点 0 到节点 2、节点 0 到 节点 3……（以此类推）的最短路径。

初始的距离列表如下：

• 源节点到它自身的距离为 0。示例中的源节点定为节点 0，不过你也可以选择任意其它节点作为源节点。
• 源节点到其它节点的距离还没有确定，所以先标记为无穷大。

还有一个列表用来记录哪些节点未被访问（即尚未被包含在路径中）：

💡 提示： 记住，当所有节点都被添加到路径中时，算法的计算过程就完成了。

我们选择了从节点 0 出发，可以直接将它标记为“已访问”，同样的，在未访问节点列表中把它划掉，并在图中给它加上红色的边框：

现在需要检查节点 0 到相邻节点的距离，两个相邻节点分别是节点 1 和节点 2（注意看红色的边）：

💡 提示： 这并不是说立即把这两个相邻节点加入到最短路径中。在把一个节点加入到最短路径之前，需要确认是否已经寻找到了访问它的最短路径。现在只是在对可选方案做初步检查。

更新节点 0 到节点 1、节点 0 到节点 2 的距离为它们之间的边的权重，分别为 2 和 6：

更新了到相邻节点的距离之后：

• 根据已知的距离列表选择距离源节点最近的节点。
• 将它标记为“已访问”。
• 将它添加到路径中。

查看距离列表，发现节点 1 到源节点的距离是最短的（距离为 2），所以把它加入到路径中。

在图中，以红色边来表示：

在距离列表中用红色方块标记这个节点，表明它是“已访问”的、已经寻找到了访问这个节点的最短路径：

在未访问节点列表中将它划掉：

现在分析新的相邻节点，寻找访问它们的最短路径。只需要分析已经在最短路径（标记为红色边）中的节点的相邻节点。

节点 2 和节点 3 都是最短路径包含的节点的相邻节点，因为它们分别与节点 0 和节点 1 直接相连，如下图所示。下一步将要分析这两个节点。

之前已经计算过源节点到节点 2 的距离，并记录在了列表中，所以不用更新。这次只需要更新源节点到新的相邻节点（节点 3）的距离：

这个距离是 7，来看看为什么。

为了计算源节点到另一个节点（这里指节点 3）的距离，需要把访问该节点的最短路径的所有边权重相加：

• 对于节点 3： 将构成路径 0 -> 1 -> 3 的所有边权重相加，得到总距离为 7（0 -> 1 距离为 2，1 -> 3 距离为 5）。

现在得到了到相邻节点的距离，需要选择一个节点添加到路径中。我们必须选择一个已知到源节点距离最短的未访问节点。

从距离列表中可以看出，距离为 6 的节点 2 就是我们的选择：

在图中为它加上红色边框，并将路径上的边标记为红色：

在距离列表中用红色方块把它标记为“已访问”，在“未访问”节点列表中把它划掉：

重复前面的步骤，寻找源节点到新的相邻节点节点 3 的最短路径。

可以看到，有两种可选的路径：0 -> 1 -> 3 或 0 -> 2 -> 3。一起看看我们是如何确定最短路径的。

节点 3 在之前已经有了一个距离记录（距离为 7，参阅下表），这个距离是之前步骤中由路径 0 -> 1 -> 3 的两个边权重（分别为 5 和 2）相加得到的。

不过现在有了一个新的可选路径：0 -> 2 -> 3，它途经权重分别为 6 和 8 的两条边 0 -> 2 和 2 -> 3，总距离为 14。

显然，第一个路径的距离更短（7 vs. 14），所以选择第一个路径 0 -> 1 -> 3。只有在新的路径距离更短的情况下，才会更新距离列表。

因此，使用第一种方案 0 -> 1 -> 3，将节点添加到路径中。

把这个节点标记为“已访问”，在“未访问”节点列表中把它划掉：

重复前面的过程。

检查尚未访问的相邻节点：节点 4 和节点 5，因为它们是节点 3 的相邻节点。

更新它们到源节点的距离，尝试寻找更短的路径：

• 对于节点 4： 路径是 0 -> 1 -> 3 -> 4，距离为 17。
• 对于节点 5： 路径是 0 -> 1 -> 3 -> 5，距离为 22。

💡 提示： 注意我们只能从最短路径（红色边）上进行扩展，而不能途经未被包含在最短路径中的边（例如，不能构造经过边 2 -> 3 的路径）。

现在需要选择将哪个未访问节点标记为“已访问”，这里选择节点 4，因为在距离列表中它的距离最短。在图中做标记：

在距离列表中用红色方块将它标记为“已访问”：

在“未访问”节点列表中把它划掉：

再次重复前面的过程。检查相邻节点：节点 5 和节点 6。分析每一种从已访问节点到它们之间的可能路径方案。

对于节点 5：

• 第一种选择是路径 0 -> 1 -> 3 -> 5，到源节点的距离为 22（2 + 5 + 15），前面的步骤已经记录了这个距离。
• 第二种选择是路径 0 -> 1 -> 3 -> 4 -> 5，到源节点的距离为 23（2 + 5 + 10 + 6）。

显然，第一个路径距离更短，为节点 5 选择第一种方案。

对于节点 6：

• 可选的路径是 0 -> 1 -> 3 -> 4 -> 6，到源节点的距离为 19（2 + 5 + 10 + 2）。

把距离最短（当前已知）的节点 6 标记为“已访问”。

在“未访问”节点列表中把它划掉：

现在得到了如下路径（标记为红色）：

现在只剩下一个节点 5 还没被访问了，看看我们要如何把它添加到路径中。

从已经添加到路径中的节点出发，有三种不同的路径可以访问节点 5：

• 第一种选择： 0 -> 1 -> 3 -> 5，总距离为 22（2 + 5 + 15）。
• 第二种选择： 0 -> 1 -> 3 -> 4 -> 5，总距离为 23（2 + 5 + 10 + 6）。
• 第三种选择： 0 -> 1 -> 3 -> 4 -> 6 -> 5，总距离为 25（2 + 5 + 10 + 2 + 6）。

选择总距离为 22 的最短路径：0 -> 1 -> 3 -> 5。

把这个节点标记为“已访问”，并在“未访问”节点列表中把它划掉：

瞧！ 我们得到了从节点 0 到图中每个节点的最短路径。

图中，标记为红色的边表示最短路径：连接节点 0 和目标节点的红色边即为从源节点出发访问目标节点的最短路径。

例如，想要从节点 0 出发访问节点 6，连接它们的红色边就是最短路径，跟着走就行了。

🔸 总结

• 图可以用来建模对象、人或实体之间的连接。它有两个关键要素：节点和边，节点表示对象，边表示对象之间的连接。
• Dijkstra 算法能够寻找出图中指定节点（“源节点”）到所有其他节点的最短路径。
• Dijkstra 算法利用边的权重来做计算，寻找源节点到所有其他节点的总距离最短（总权重最小）的路径。

希望你喜欢我的文章并且有所收获。 想必你现在已经理解了 Dijkstra 算法背后的工作原理了。欢迎关注我的 Twitter @EstefaniaCassN 或查看我的在线课程。

原文：Dijkstra's Shortest Path Algorithm - A Detailed and Visual Introduction，作者：Estefania Cassingena Navone