冒泡排序（也称为Exchange排序）是一种简单的排序算法。它的工作方式是重复遍历要排序的列表, 一次比较两个项目, 如果顺序错误则交换它们。重复遍历列表, 直到不需要交换为止, 这意味着对列表进行了排序。
这是所有排序算法中最简单的方法。
BUBBLE SORT (A)
1. for i ← 1 to length [A]
2. for k ← length [A] down to i+1
3. if A[k] <
A[k-1]
4. exchange (A[k], A [k-1])分析
- 输入：给出n个元素。
- 输出：进行排序所需的比较数。
- 逻辑：如果在气泡排序中有n个元素, 则需要n-1次通过才能找到排序后的数组。
In pass 1: n-1 comparisons are required
In pass 2: n-2 comparisons are required
In pass 3: n-3 comparisons are required
............................................................................
...............................................................................
In pass n-1: 1 comparisons is required
Total comparisons: T (n) = (n-1) + (n-2) +...........+ 1
=
= o (n2)
Therefore complexity is of order n2例：
【冒泡排序算法】未排序清单：A = {7, 2, 1, 4, 4, 5, 9, 6}
即A [] =
| 7 | 2 | 1 | 4 | 3 | 6 | 9 |
Here length [A] =7
i=1 to 7 and j=7 to 2
i=1, j=7
A [7] =6 and A [6] =9. So A [7] <
A [6]
Now Exchange (A [7], A [6])
Now, i=1, j=6 then A [6] =6
A [5] = 3 and A [5] <
A [6]
Now, i=1, j=5 then A [5] = 3
A [4] = 4 and A [5] <
A [4]
So, exchange (A [5], A [4])和A [] =
| 7 | 2 | 1 | 3 | 4 | 6 | 9 |
Now, i=1, j=4 then A [4] =3
A [3] = 1 and A [4] >
A [3]
Now, i=1, j=3 then A [3] = 1
A [2] = 2 and A [3] <
A [2]
So, exchange (A [3], A [2])然后A [] =
| 7 | 1 | 2 | 3 | 4 | 6 | 9 |
Now, i=2, j-2 then A [2] =1
A [1] =7 and A [2] <
A [1]
So, exchange (A [2], A [1])然后A [] =
| 1 | 7 | 2 | 3 | 4 | 6 | 9 |
Now, i=1, j=7 then A [7] =9
A [6] =6 and A [7] >
A [6], No Exchange
Similarly, i=2, j=6, 5, 4. No change.
Then i = 2, j=3
A [3] = 2
A [2] = 7 and A [3] <
A [2]
So, exchange (A [3], A [2])和A [] =
| 1 | 2 | 7 | 3 | 4 | 6 | 9 |
Now, i=3, j=5, 6, 7 No change
Then i=3, j=4
A [4] = 3
A [3] = 7and A [4] <
A [3]
So, exchange (A [4], A [3])然后A [] =
| 1 | 2 | 3 | 7 | 4 | 6 | 9 |
Now, i=4, j= 6, 7 No change
Now, i=4, j=5 then A [5] = 4
A [4] = 7 and A [5] <
A [4]
So exchange (A [5], A [4])和A [] =
| 1 | 2 | 3 | 4 | 7 | 6 | 9 |
Now, i=5, j= 6, 7 No change
Now, i=5, j=6 then A [6] = 6
A [5] = 7
and A [6] <
A [5]
So exchange (A [6], A [5])和A [] =
| 1 | 2 | 3 | 4 | 6 | 7 | 9 |
