【白话排序算法】冒泡排序法

叁歲伎倆 2022-12-24 10:59 157阅读 0赞

冒泡排序是一种非常容易理解的排序方式。比如以下的待排序数组：

var seq = [9, 2, 6, 4, 3, 1, 7, 5, 6];

通过对数组进行遍历，每一趟遍历都依次从左至右两个两个的元素进行比较，若二者次序不正确，就交替二者的位置，描述起来略显枯燥，请看以下图例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ1OTg2Ng_size_16_color_FFFFFF_t_70]  
上图由左至右，为一趟排序，观察`9`这个数字其实已经排序到最终的位置。而且整个过程是不是像`9`这个数字从底部上升到顶部？其实次大的`7`也会在第二趟排序中从他现有的位置上升到顶部第二的位置。整体就像一个个气泡从水底逐渐冒泡到顶部的过程，故名冒泡排序。

可以看到冒泡排序的核心就是每一趟遍历**若前者大于后者，则交换二者的位置**。当遍历完成即完成了排序的过程，下面我用javascript语言来实现：

怎么样，够简单吧。但是呢，还有一个可优化的点。即若序列本身已经是有序的，那么冒泡排序一趟下来实际上并未发生任何交换。而且之后的每一趟都不会发生交换。

即，**若在某一趟排序完成之后，若发现本趟排序并未移动任何元素。那么可以认定当前的序列已经有序。**

接下来稍微改动一下代码如下：

如上，若队列已经有序，仅仅会执行一次遍历。所以冒泡排序也适合那种本身已经部分有序的情况。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ1OTg2Ng_size_16_color_FFFFFF_t_70]: /images/20221120/f97ecf62e8c841d082a055e9b4576b30.png