它重复地走访过要排序的数组,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数组已经排序完成。排序的过程就像把元素慢慢的“浮”到顶端一样,故名“冒泡排序”

流程

原数组:5          6          3         1         2        9        8         6        10         1

第一轮

5          6          3         1         2        9        8         6        10        1

5          3          6         1         2        9        8         6        10        1

5          3          1         6         2        9        8         6        10        1

5          3          1         2         6        9        8         6        10        1

5          3          1                 6        9        8         6        10        1

5          3          1                 6        8        9         6        10        1

5          3          1                 6        8        6         9        10        1

5          3          1                 6        8        6         9        10        1

5          3          1                 6        8        6         9        1          10

一共比较 9 次,元素 10 归位

第二轮

3         5          1                 6        8        6         9        1          10

       1          5                 6        8        6         9        1          10

       1          2         5         6        8        6         9        1          10

       1          2         5         6        8        6         9        1          10

       1          2         5         6        8        6         9        1          10

       1          2         5         6        6        8         9        1          10

       1          2         5         6        6        8         9        1          10

       1          2         5         6        6        8         1        9          10

一共比较 8 次,元素 9,10 归位 (PS:上一轮10已经归位,只需要比较8次)

………

第九轮

1         1          2         3         5        6        6         8        9          10

一共比较 1 次,元素全部归位 (PS:最后一轮只需一次即可搞定)

总结:从上面流程可以看出冒泡排序一共需要进行 n-1 轮,每轮进行 n-i 次比较 (n:数组长度,i:第几轮),So,冒泡排序的代码也很easy了。

代码(C#)

 

优化1

通过上面代码不难发现,如果是已经正序的数组,还得徒劳的进行两两比较。所以,我们增加一个状态,如果一轮下来发现没有两个元素进行交换(即状态没有改变),我们就可以认为该数组已经成功排序。So, 代码进行稍稍的改变。

优化2

网上也有人进行了进一步优化,在某种特例下,比如:8  1  6  2  5  4  3  7  1  9  10  11  12  13  14  15  16  17  18  19  20 这个数组,你会发现从9开始后面是有序的元素。我们可以试着缩短一下比较的次数(内循环),第一轮循环,最后交换的是7和1,然后7后面全都是有序元素,把原数组的7位置记住,下次只需要循环到此位置即可。

总结

  • 冒泡排序未优化之前,比较次数为(N-1)+……+3+2+1=N(N-1)/2
  • 时间复杂度为O(n²)
  • 稳定性:稳定,如:5  8  5  2  6
  • 优化后,最好时间复杂度为O(n)
  • 冒泡排序是一种低效的排序算法,数据量小的时候可以使用,数据量大时请换成其他排序方式。

如果转载,请给出原文链接,谢谢!


微信支付宝

如果本文帮助到您,请随意打赏作者