【庖丁解题】排序算法之冒泡排序剖析

转载声明：商业转载请联系作者获得授权,非商业转载请注明出处.原文来自 © 呆萌钟【庖丁解题】排序算法之冒泡排序剖析

前言

排序算法一直是面试的高频考点，但是如果没有真正理解不同算法的原理，光靠硬背，很容易到需要用的时候就忘记了。要想灵活运用并熟记各种算法，前提是必须去理解它们。那接下来，我就带大家抽丝剥茧，剖析那些经典算法！

冒泡排序

冒泡排序是所有排序中最常出现的，所以这篇文章我先为大家讲解冒泡排序。

概述（百度百科）

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法原理

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图解

光看百度百科的解释还是比较难以理解吧，那我们用图形的形式来表述这个原理，相信你立马会恍然大悟。

首先，我们准备一组需要进行排序的数据。

然后，根据上面的算法原理，我们进行第一轮比较

执行完第一轮排序之后，拿第一轮排序完之后的结果进行第二轮排序

重复上述操作，执行第三轮排序

执行第四轮

第四轮执行完毕之后，我们可以发现，所有的相邻元素我们都比较过了一遍，而且此时第四轮的结果已经是呈现升序排序了。如果把每个元素看成一个气泡，值越大的数据泡泡越大，并且大的泡泡都往上冒，可以理解为如下图：

这就是冒泡排序的原理，此时在结合上面的算法原理，是不是觉得如此简单呢？

代码实现

好了，前面我们已经根据图文并茂的形式理解了冒泡排序的原理，那接下来我们要做的就是如何把它转换成代码输出，我这边用Java代码为例。

分析

比较相邻的元素。如果第一个比第二个大，就交换他们两个

代码表现如下：

if (arr[i]>arr[i+1]) {//比较相邻的元素
    //交换
    int temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
}
           

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对

意味着要用循环遍历去比较

for(int i=0;i<arr.length;i++){
    if (arr[i]>arr[i+1]) {//比较相邻的元素
        //交换
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
  }
           

但是这段代码有一个问题，当i=arr.length-1时，也可理解为比较到最后一个元素时，i+1将会等于arr.length，这会导致arr[i+1]报数组下标越界异常，所以我们需要限定循环的范围是小于arr.length-1，代码标识如下：

for(int i=0;i<arr.length-1;i++){
  if (arr[i]>arr[i+1]) {//比较相邻的元素
      //交换
      int temp = arr[i];
      arr[i] = arr[i+1];
      arr[i+1] = temp;
  }
}
           

然而，以上代码只能实现第一轮排序。但是我们观察图解部分的每轮排序的图片，可以发现，我们总共进行了四轮排序，所以可以得出结论需要执行的排序轮数等于数组长度减1.

for(int k=0;k<arr.length-1;k++){//外层循环控制排序轮数
            for(int i=0;i<arr.length-1;i++){//内层循环控制每一轮的排序次数
                if (arr[i]>arr[i+1]) {//比较相邻的元素
                    //交换
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }
           

执行完上述代码，我们会发现我们的数组已经排好序了。你以为这就万事大吉了？NO，我们再来看看图解部分的图片，可以发现，每一轮比较的次数都比上一轮少了一次。第一轮4次，第二轮3次，第三轮2次，第四轮1次。所以，我们上面的代码虽然实现了排序，但是每次还会比较已经排好序的元素，增加了时间复杂度。所以我们应该在每轮排序的时候减去那些已经排好序的元素，只比较未排好序的元素。经过分析，我们可以发现，第一轮排好序的元素为0个，第二轮1个，第三轮2个，第四轮3个，所以我们可以得出结论，每轮排好序的元素与轮次成正比，我们只需要在每轮比较排序之前减去已经排好序的元素个数就可以了. 例如：

第一轮需要比较的元素个数:arr.length-0
第二轮需要比较的元素个数:arr.length-1
第三轮需要比较的元素个数:arr.length-2
第四轮需要比较的元素个数:arr.length-3
           

由此我们可以得出如下代码

for(int k=0;k<arr.length-1;k++){//外层循环控制排序轮数
            for(int i=0;i<arr.length-1-k;i++){//内层循环控制每一轮的排序次数
                if (arr[i]>arr[i+1]) {//比较相邻的元素
                    //交换
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }
           

以上代码就是冒泡排序的最终实现。

总结

通过图解加理论加推演分析，是不是觉得冒泡排序不过如此？相信你看完这篇文章，妈妈再也不用担心我写不出冒泡排序了~