冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述
- 比较相邻的元素。如果前面的数比后面的数大(按升序排序)，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样最大的元素就放在了最后面；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
动图演示
![]()
算法分析
最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)
代码实现
Java
Java 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
System.out.printf("排序第%2d次后数组为：%s\n", i + 1, Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
System.out.printf("原始数组：%s\n", Arrays.toString(arr));
bubbleSort(arr);
System.out.printf("排序后数组：%s\n", Arrays.toString(arr));
}
}
|
Python
Python 实现1
2
3
4
5
6
7
8
9
10
11
12
13
| def bubble_sort(arr):
for i in range(0, len(arr) - 1):
for j in range(0, len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
print('排序第%2d次后数组为：%s' % (i + 1, arr))
if __name__ == '__main__':
arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print('原始数组：', arr)
bubble_sort(arr)
print('排序后数组：', arr)
|
Go
Go 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| package main
import (
"fmt"
)
func BubbleSort(arr *[15]int) {
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
fmt.Printf("排序第%2d次后数组为：%v\n", i+1, *arr)
}
}
func main() {
arr := [15]int{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
fmt.Printf("原始数组：%v\n", arr)
BubbleSort(&arr)
fmt.Printf("排序后数组：%v\n", arr)
}
|
为什么最佳情况是 O(n)
上面说过冒泡排序最佳情况是O(n)，这点我一开时很不理解，看上面代码实现，即便一开始已经是按顺序排序的，但最终还是要经过两层循环，也就是最佳情况依然是O(n2)。实际上，上面的代码是可以优化的，下面以Go语言来实现：
Go 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| package main
import (
"fmt"
)
func BubbleSort(arr *[15]int) {
flag := false
for i := 0; i < len(arr)-1; i++ {
flag = false
for j := 0; j < len(arr)-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
flag = true
}
}
fmt.Printf("排序第%2d次后数组为：%v\n", i+1, *arr)
if !flag {
break
}
}
}
func main() {
arr := [15]int{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
fmt.Printf("原始数组：%v\n", arr)
BubbleSort(&arr)
fmt.Printf("排序后数组：%v\n", arr)
}
|
上面的代码，在数组已经从小到大排序的情况下，只需经过一轮循环遍历即可，也就是最佳情况为O(n)。
