你确定懂冒泡排序？用动画的方式讲懂冒泡排序及其优化方式

绝地灬酷狼 2023-10-13 09:29 6阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th><a href="https://www.coding-time.cn" rel="nofollow">点击在线阅读，体验更好</a></th> 
   <th><a href="https://www.coding-time.cn" rel="nofollow">链接</a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong><a href="https://www.coding-time.cn" rel="nofollow">现代JavaScript高级小册</a></strong></td> 
   <td><a href="https://www.coding-time.cn" rel="nofollow">链接</a></td> 
  </tr> 
  <tr> 
   <td><strong><a href="https://www.coding-time.cn" rel="nofollow">深入浅出Dart</a></strong></td> 
   <td><a href="https://www.coding-time.cn" rel="nofollow">链接</a></td> 
  </tr> 
  <tr> 
   <td><strong><a href="https://www.coding-time.cn" rel="nofollow">现代TypeScript高级小册</a></strong></td> 
   <td><a href="https://www.coding-time.cn" rel="nofollow">链接</a></td> 
  </tr> 
 </tbody> 
</table>

### 基本概念 ###

> 冒泡排序是一种基础的排序算法。其基本思想是通过不断地比较相邻元素并在必要时进行交换，将最大（或最小）的元素"冒"到序列的一端。

### 排序步骤 ###

> 先来感受到冒泡排序的步骤吧

以数组 `[5, 3, 8, 4, 6]`为例，冒泡排序的步骤如下：

*  **第一轮排序：**

比较相邻的元素。第一次比较5和3，5大于3，交换它们两个，数组变成 `[3, 5, 8, 4, 6]`；接着比较5和8，5小于8，不用交换，然后比较8和4，8大于4，交换，数组变为 `[3, 5, 4, 8, 6]`；最后比较8和6，8大于6，交换，数组变为 `[3, 5, 4, 6, 8]`。这样，第一轮比较结束后，最大的数8被排到了最后。

*  **第二轮排序：**

再次从前向后比较相邻的元素，这次因为8已经是最大的元素在末尾，所以不再参与比较。先比较3和5，3小于5，不用交换；然后比较5和4，5大于4，交换，数组变为 `[3, 4, 5, 6, 8]`；接着比较5和6，5小于6，不用交换。这样，第二轮排序结束，第二大的元素6也排到了它应该在的位置。

*  **后续轮排序：**

如此反复进行，每一轮比较的元素对都比上一轮少一对。直至完成所有的排序。

最终，数组 `[5, 3, 8, 4, 6]` 被排序为 `[3, 4, 5, 6, 8]`。

### 冒泡排序的实现 ###

此算法的时间复杂度为O(n^2)，因此在处理大量数据时可能效率较低。

### 优化策略 ###

#### 交换标记 ####

> 如果在一次遍历过程中没有发生过交换，那么意味着序列已经是有序的，不需要继续排序。我们可以通过设置一个标记来优化算法。如果在某次遍历中没有发生交换，则直接结束排序。

这个优化对于已经部分有序的序列来说，可以大幅度提高效率。

#### 双向冒泡排序 ####