前言

算法这个领域可以说是我个人的一个盲点，从朋友口中得知在中大厂面试中对算法的考察越来越高了。这也让我觉得很焦虑，于是开始查阅资料学习算法，在学习的过程中我发现有一些算法实现起来很巧妙但因为算法本身比较抽象所以理解起来是非常困难的，因此我把解析步骤总结出来写成文章以便后面复习加深记忆，如果你感兴趣的话就接着往下看吧。

插图

什么是冒泡排序？

“冒泡排序”这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端特别像水泡从水底冒到水面。下面我们来看一段算法解析。

算法解析

给定一个 N 个元素的数组，冒泡法排序将：

1. 比较一对相邻元素（a，b），
2. 如果两项的大小关系不正确，交换这两个数（在本例中为a > b），
3. 重复步骤1和2，直到我们到达数组的末尾（最后一对是第 N-2 和 N-1 项，因为我们的数组从零开始）
4. 到目前为止，最大项将在最后的位置。 然后我们将 N 减少1，并重复步骤1，直到 N = 1

代码实现

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // 一轮排序下来最后一个放置的是最大值,下一轮不需要对最后一位进行排序
    // debugger
    for (let j = 0; j < arr.length -i - 1; j++) {
      // 前后位置交换
      if(arr[j] > arr[j+1]){
        // var tem = arr[j];
        // arr[j] = arr[j+1];
        // arr[j+1] = tem;
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]] 
      }
    }
  }
}

export default bubbleSort

过程解析

假设有一个需要排序的数组 arr: [29, 23, 43, 9, 7, 49, 36, 17] 设外层循环索引为i,内层循环索引为j,相邻元素分别为a和b

• 第一轮排序: i: 0

  1. 内循环第1轮排序: j: 0｜a: 29｜b: 23
     a > b: true 进行交换
     arr: [23, 29, 43, 9, 7, 49, 36, 17]

  2. 内循环第2轮排序:

     j: 1 a: 29 b: 43
     a < b: true 不交换直接进入下一循环
     arr: [23, 29, 43, 9, 7, 49, 36, 17]

  • 内循环第3轮排序:

    j: 2 ｜ a: 43｜ b: 9
    a > b: true 进行交换
    arr: [23, 29, 9, 43, 7, 49, 36, 17]

  • 内循环第4轮排序:

    j: 3｜a: 43｜b: 7
    a > b: true 进行交换
    arr: **[23, 29, 9, 7, 43, 49, 36, 17] **

  • 内循环第5轮排序:

    j: 4 ｜a: 43 ｜b: 49
    a < b: true 不交换直接进入下一循环
    arr: [23, 29, 9, 7, 43, 49, 36, 17]

  • 内循环第6轮排序:

    j: 5｜a: 49｜b: 36
    a > b: true 进行交换
    arr: [23, 29, 9, 7, 43, 36, 49, 17]

  • 内循环第7轮排序:

    j: 6｜a: 49｜b: 17
    a > b: true 进行交换
    arr: [23, 29, 9, 7, 43, 36, 17, 49]

经过一轮排序下来我们发现最后一位放置的是最大值,下一轮不需要对最后一位进行排序 后面的循环其实都是重复执行之前的步骤内层循环的详细排列我就给省略了直接给出外层循环的结果

• 第一轮排序: arr :[23, 29, 9, 7, 43, 36, 17, 49]
• 第二轮排序: arr :[23, 9, 7, 29, 36, 17, 43, 49]
• 第三轮排序: arr: [9, 7, 23, 29, 17, 36, 43, 49]
• 第四轮排序: arr: [7, 9, 23, 17, 29, 36, 43, 49]
• 第五轮排序: arr: [7, 9, 17, 23, 29, 36, 43, 49]
• 第六轮排序: arr: [7, 9, 17, 23, 29, 36, 43, 49]
• 第六轮排序: arr: [7, 9, 17, 23, 29, 36, 43, 49]
• 第七轮排序: arr: [7, 9, 17, 23, 29, 36, 43, 49]

值得一提的是第五轮排序完成后其实整个数组已经是个有序的状态了,但是无论是外层循环还是内层循环都依然继续执行了，是因为程序不知道当前数组已经是个有序的状态了，所以如果能找到这个有序的点那么冒泡排序还可以进行优化让我们接着往下看。

优化

从上面的示例可以知道冒泡排序它可以提前结束的，改进的思路很简单：如果某次内部循环完全不交换，这意味着数组已经有序，我们可以在这个点上停止冒泡排序。

冒泡排序优化如下:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // 一轮排序下来最后一个放置的是最大值,下一轮不需要对最后一位进行排序
    // debugger
    let flag = true // flag：若一次排序未发现数据交换，则说明数据已经有序，可以结束排序过程
    for (let j = 0; j < arr.length -i - 1; j++) {
      // 前后位置交换
      if(arr[j] > arr[j+1]){
        // var tem = arr[j];
        // arr[j] = arr[j+1];
        // arr[j+1] = tem;
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        flag = false // 如果发生过排序则当说明前并非有序数组，循环继续
      }
    }
    if(flag){
      break
    }
  }
}

export default bubbleSort

至此我们完成了冒泡排序的实现以及优化同时也是自己职业生涯中第一个算法的实现。

最后，感谢您阅读这篇文章，有任何问题或反馈请给我留言。