冒泡排序就这么简单

冒泡排序就这么简单

在我大一的时候自学c语言和数据结构，我当时就接触到了冒泡排序(当时使用的是C语言编写的)。现在大三了，想要在暑假找到一份实习的工作，又要回顾一下数据结构与算法的知识点了。

排序对我们来说是一点也不陌生了，当你打王者荣耀的时候也会有段位之分，当你打Dota的时候也有天梯分。从高往下数，这个排名是有规律的，就是一种排序。

我最开始接触的就是冒泡排序，所以这篇博文主要讲的是冒泡排序。

冒泡排序的实现

来源百度百科：

冒泡排序（Bubble Sort，中国台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

算法描述：

从0开始，与比较，如果，那么就互换

不断增加，直到（n是数组元素的个数，是数组已经最后一个元素） ，一趟下来，可以让数组元素中最大值排在数组的最后面

从最简单开始，首先我们创建一个数组，该数组有5位数字：

一、第一趟排序

下面我们根据算法的描述来进行代码验算(第一趟排序)：

如果前一位的数比后一位的数要大，那么就交换，直到将数组的所有元素都比较了一遍！

经过我们第一趟比较，我们可以发现：最大的值就在数组的末尾了!

一、第二趟排序

第二趟排序跟第一趟排序一样，也是用前一位与后一位比较，如果前一位比后一位要大，那就交换。值得注意的是：并不需要与最后一位比较了，因为在第一趟排序完了，最后一位已经是最大的数了。同理，我们第二趟排序完了之后，倒数第二位也是第二大的数了。

第二趟排序的代码如下：

结果：我们的第二大数已经排在了倒数第二位了

三、代码简化

值得说明的是：上面的结果看起来已经是排序好的了，其实是我在测试时数据还不足够乱，如果数据足够乱的话，是需要4(n-1)趟排序的！

但我们从上面的代码就可以发现：第一趟和第二趟的比较、交换代码都是重复的，并且我们的比较都是写死的(0,1,2,3,4)，并不通用！

我们的数组有5位数字

第一趟需要比较4次

第二趟需要比较3次

我们可以根据上面规律推断出：

第三趟需要比较2次

第四躺需要比较1次

再从上面的规律可以总结出：5位数的数组需要4躺排序的，每躺排序之后次数减1(因为前一趟已经把前一趟数的最大值确定下来了)！

于是我们可以根据for循环和变量将上面的代码进行简化：

四、冒泡排序优化

从上面的例子我们可以看出来，如果数据足够乱的情况下是需要经过4躺比较才能将数组完整排好序。但是我们在第二躺比较后就已经得到排好序的数组了。

但是，我们的程序在第二趟排序后仍会执行第三趟、第四趟排序。这是没有必要的，因此我们可以对其进行优化一下：

如果在某躺排序中没有发生交换位置，那么我们可以认为该数组已经排好序了。

这也不难理解，因为我们每趟排序的目的就是将当前趟最大的数置换到对应的位置上，没有发生置换说明就已经排好序了。

代码如下：