冒泡排序(Bubble Sort)算法又称为泡沫排序算法,是基本的排序算法,是学习编程语言最先需要学会的排序算法之一。顾名思义,就是它的排序方式如同气泡一般,不断将最大的元素挤出(移动)到串行最尾端,当所有元素都被挤出后,排序就完成了!而且排序结果是稳定的。
冒泡排序法(Bubble Sort)
冒泡排序法的概念
冒泡排序法会从串行最前方开始进行走访,在每次迭代时,会拿当前索引位置的元素与其下一个索引位置的元素进行比较,如果下一个元素比较小,就进行交换;如果下一个元素没有比较小,就不进行交换。当串行被走访完一次之后,串行的最尾端元素即为最大的元素。再来重新走访一次串行,用同样的方法将第二大的元素值挤进串行的从尾端开始倒数的第二个位置。然后重新走访一次串行,用同样的方法将第三大的元素值挤进串行的从尾端开始倒数的第三个位置。依此类推,直到所有元素都被挤到尾端,或是在走访串行的过程中,如果发现都没有元素被交换的话,表示此时的串行已经完成排序了。
冒泡排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
一开始,要将重点聚焦于数组最尾端的位置,因为我们要先将整个数组的最大值移动到数组的最尾端。
从数组最前方开始,逐次两两比较元素的大小,将两个元素中较大的元素排在后面,即可逐渐将最大的元素从数组前方挤到数组后方。这就像是沉在水中的大气泡,想要漂浮到水面上前,必须挤开其它的小气泡一样。
所以,若要挤出数组的最大值至数组的最尾端,位于数组最前端的 69,要跟它之后的元素 81 比大小,如下表:
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
由于 69 比 81 小,所以不用换位置。然后再比 81 和 30 的大小,如下表:
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
81 > 30
81 比 30 大,所以 81 会挤开 30,与 30 交换,排在 30 之后。
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└─┘
然后再比较 81 和 38 的大小,如下表:
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└┬┘
81 > 38
81 比 38 大,所以 81 会挤开 38,与 38 交换,排在 38 之后。
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└─┘
继续判断大小并移动,直到最大值被挤到数组最尾端:
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└┬┘
81 > 9
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└┬┘
81 > 2
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└┬┘
81 > 47
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└┬┘
81 > 61
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└┬┘
81 > 32
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└┬┘
81 > 79
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
如此一来,数组中的最大元素 81 就成功被挤出至最尾端了。接着用同样的方法继续找出第二大的元素,并将其挤出至从尾端开始倒数的第二个位置,再找出第三大的元素,并将其挤出至从尾端开始倒数的第三个位置。直到所有元素都被挤出为止,数组就排序完成了!完整过程如下:
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
81 > 30
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└┬┘
81 > 38
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└┬┘
81 > 9
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└┬┘
81 > 2
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└┬┘
81 > 47
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└┬┘
81 > 61
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└┬┘
81 > 32
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└┬┘
81 > 79
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└┬┘
69 > 30
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 38 9 2 47 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 38 9 2 47 61 32 79 81
└┬┘
69 > 38
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 9 2 47 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 9 2 47 61 32 79 81
└┬┘
69 > 9
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 69 2 47 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 69 2 47 61 32 79 81
└┬┘
69 > 2
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 69 47 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 69 47 61 32 79 81
└┬┘
69 > 47
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 69 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 69 61 32 79 81
└┬┘
69 > 61
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 61 69 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 61 69 32 79 81
└┬┘
69 > 32
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 61 32 69 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 61 32 69 79 81
└┬┘
69 < 79
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 61 32 69 79 81
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 61 32 69 79 81
└┬┘
30 < 38
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 9 2 47 61 32 69 79 81
└┬┘
38 > 9
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 38 2 47 61 32 69 79 81
└─┘
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 38 2 47 61 32 69 79 81
└┬┘
38 > 2
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 61 32 69 79 81
└─┘
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 61 32 69 79 81
└┬┘
38 < 47
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 61 32 69 79 81
└┬┘
47 < 61
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 61 32 69 79 81
└┬┘
61 > 32
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 32 61 69 79 81
└─┘
● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 32 61 69 79 81
└┬┘
61 < 69
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 32 61 69 79 81
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 9 2 38 47 32 61 69 79 81
└┬┘
30 > 9
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 2 38 47 32 61 69 79 81
└─┘
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 2 38 47 32 61 69 79 81
└┬┘
30 > 2
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 47 32 61 69 79 81
└─┘
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 47 32 61 69 79 81
└┬┘
30 < 38
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 47 32 61 69 79 81
└┬┘
38 < 47
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 47 32 61 69 79 81
└┬┘
47 > 32
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 32 47 61 69 79 81
└─┘
● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 32 47 61 69 79 81
└┬┘
47 < 61
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 32 47 61 69 79 81
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 2 30 38 32 47 61 69 79 81
└┬┘
9 > 2
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
└─┘
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
└┬┘
9 < 30
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
└┬┘
30 < 38
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
└┬┘
38 > 32
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└─┘
● ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
38 < 47
● ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
● ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
2 < 9
● ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
9 < 30
● ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
30 < 32
● ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
32 < 38
● ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
※
冒泡排序法的程序实作
冒泡排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n^2)}}# | 排序已经反向排序过的串行。 |
| 最佳时间复杂度 | #{{O(n)}}# | 排序已经正向排序过的串行。 |
| 平均时间复杂度 | #{{O(n^2)}}# | |
| 最差空间复杂度 | #{{O(1)}}# | |
| 是否稳定 | 是 |

