决胜经典算法之冒泡排序

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

  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. 如果要实现从大到小排列,上述代码该做如何修改呢?

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

posted @ 2019-09-16 15:24 萧文翰 阅读(...) 评论(...) 编辑 收藏
聚福彩票网 605| 932| 542| 581| 134| 929| 851| 56| 938| 728| 440| 875| 869| 56| 524| 500| 449| 944| 605| 962| 347| 803| 11| 329| 878| 776| 728| 515| 572| 629|