决胜经典算法之冒泡排序

本篇是《决胜经典算法》系列文章的第一篇,作为开篇,先向各位读者说明一下本系列的几个“原则”。由浅入深:刚一开始将会分享很易懂、易于理解的算法。比如本文讲述的冒泡排序法就可以称得上是最为简单的算法了;思路优先,代码为辅:对于任何一种算法,可以说思路是最重要的。有了思路,相当于成功了一半。另外,虽然不同的程序语言的语法等有所差异,但解题思路是大体一致的。因此,在摆出实际代码前,会详细地说明解题思路;更...

决胜经典算法之冒泡排序

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

  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   endend

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[j1]) { int temp = arr[j]; arr[j] = arr[j1]; arr[j1] = temp;}  } }}

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

思考题

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

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

源文地址:https://www.guoxiongfei.cn/cntech/27158.html