决胜经典算法之冒泡排序

本篇是《决胜经典算法》系列文章的第一篇，作为开篇，先向各位读者说明一下本系列的几个“原则”。

1. 由浅入深：刚一开始将会分享很易懂、易于理解的算法。比如本文讲述的冒泡排序法就可以称得上是最为简单的算法了；
2. 思路优先，代码为辅：对于任何一种算法，可以说思路是最重要的。有了思路，相当于成功了一半。另外，虽然不同的程序语言的语法等有所差异，但解题思路是大体一致的。因此，在摆出实际代码前，会详细地说明解题思路；
3. 更易理解的图示：本系列文章会尽可能地多采用图示甚至动图来解释算法中的每一步，让读者理解起来更加直观。

第一部分，我们来聊一聊排序。单说排序算法，有近十种。不同的算法对应不同的应用场景（有关不同排序算法的性能比较，将在完整介绍完10种排序算法后统一说明）。
闲话少说，接下来我们就来看第一种排序算法，也是本系列中最为简单的一种算法——冒泡排序法。

问题挑战

现有如下数字：
3，44，38，5，47，15，36，26，27，2，46，4，19，50，48
一共15个数字，请将其从小到大依次排列。

算法解析

所谓“冒泡排序”，可以从名称上理解。“冒泡”实际上就是指把值更大的元素放到数列的后面来（如果是从大到小排列，则反之），好像是这个元素“浮”了过来。我们先来大致地看下面的动图，感受一下冒泡排序的运行过程：

冒泡排序全过程

怎么样？有没有感觉到一个个值更大的元素一点点地“冒泡”到了右端？
是不是有点眼花缭乱？别着急，下面我们逐步拆解。

详细步骤

我们来看一下冒泡排序的详细步骤：

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

冒泡排序流程图

伪代码

有了详细步骤，我们就可以使用伪代码实现了，参考下面的伪代码：

BubbleSort(input ele[],input length)  
    for i <- 1 to length step 1  
        for j <- i+1 to 0 step -1  
            if ele[j] < ele [j - 1]  
                swap (ele[j],ele[j - 1])  
            end if  
    end   
end

Java代码实现

下面启动IDE，使用Java编程语言实现它吧！

public void bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

上述代码中，参数arr表示未经排序的数列。该方法运行结束后，arr将变为从小到大排序的数列。

思考题

1. 如果要实现从大到小排列，上述代码该做如何修改呢？

思考题答案将在下篇连载中公布，大家加油哦！