经典排序算法之冒泡排序的优化方案

柔情只为你懂 2022-09-12 14:52 152阅读 0赞

### 前言 ###

在前面的文章[经典排序算法之冒泡排序][Link 1]我们已经掌握了冒泡的原理和方法，但经过分析发现虽然结果是我们想要的，但却不是最优的冒泡排序，下面我们将结合前面文章中的示例进行一下冒泡的优化。

### 优化方案及思路分析 ###

> 在我们的口诀中（n-1）轮循环是一种保底的情况，就是为了保证每两个相邻值都能得到比较，但是前面文章中的示例，其实在第四轮比较就已经得到了期望结果，而后面的两轮比较完全没有必要的。再假设一种更极端的情况，假如给定的数组就已经是一个有序数组了\[1,4,7,8,10,12,21\]，那么按照口诀是不是依然还要进行6轮的循环比较呢，显然是不合理的。因此我们就应该想办法去优化一下。  
> 其实优化方案很简单，我们可以定义一个标记，在每一次进行两个数比较时，如果IF条件成立说明还没有排好序，依然需要下一轮循环，因此在这个时候我们可以打个标记，就说还没排好序，需要继续下一轮循环。那么如果每次进行比较时条件都不成立，也就是说没有需要交换位置的相邻数了，那么就不需要再打标记，这个时候就不用再继续下一轮循环了，从而也避免一些不必要的开销。废话不多说，下面直接上优化后的代码更加一目了然

> 看上面的代码，以我们最极端的情况为例，假设给定的数组就是一个有序数组：\[1,4,7,8,10,12,21\]，那么在进行第一轮for循环时，在内层循环中发现每次IF条件都不成立，也就是说从头到尾都没有两个相邻数需要交换位置，那么isSorted就一直是false，那么在内层循环结束后，在走到if(!isSorted) 时会直接跳出外层循环，也就是说整个过程只需要一轮循环就结束了，想想是不是比前面的6轮循环节省了很多开销。

### 总结 ###

> 以上就是针对冒泡排序的优化方案，喜欢的老铁可以点赞加关注喔~~~

[Link 1]: https://blog.csdn.net/lixiaosenlin/article/details/120483068