算法之排序-冒泡排序

排序算法之冒泡排序

冒泡排序是通过按照固定的设置(上升或下降)交换相邻两个元素的位置,实现排序的。

  • 时间复杂度: $O(n^2)$
  • 辅助空间: $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
目标是将数组从小到大排序,所以我们选择上升较大的元素

第一遍遍历:
(5 1 4 2 8) - >(1 5 4 2 8),这里,算法比较前两个元素,并交换5>1 。
(1 5 4 2 8) - >(1 4 5 2 8),交换5> 4
(1 4 5 2 8) - >(1 4 2 5 8),交换5> 2
(1 4 2 5 8) - >(1 4 2 5 8),元素已经按顺序排列(8> 5),算法不会交换它们。

第二次通过:
(1 4 2 5 8) - >(1 4 2 5 8)
(1 4 2 5 8) - >(1 2 4 5 8),交换4> 2
(1 2 4 5 8) - > (1 2 4 5 8)
(1 2 4 5 8) - >(1 2 4 5 8)
现在,数组已经排序,但我们的算法不知道它是否已完成。该算法需要一个完整的变例,且这过程中没有任何交换,那么可以知道它已经排序成功。

第三次通过:
(1 2 4 5 8) - >(1 2 4 5 8)
(1 2 4 5 8) - >(1 2 4 5 8)
(1 2 4 5 8) - >(1 2 4 5 8 )
(1 2 4 5 8) - >(1 2 4 5 8)

算法结束,排序成功。

代码实现见BubbleSort

-------------本文结束感谢您的阅读-------------
坚持分享,您的支持将鼓励我继续创作!
0%