排序算法之冒泡排序(Bubble Sort)

冒泡排序(Bubble Sort)

1.算法伪代码

for i = 1 : n
	swapped = false
	for j = n : i + 1
		if a[j] < a[j - 1]
			交换a[j]和a[j - 1]
			swapped = true
	排好序的数列：a[1...i]
	break if not swapped
end

2.算法过程
初始数列：5, 3, 2, 4, 1
i = 1
[
5, 3, 2, 1, 4
5, 3, 1, 2, 4
5, 1, 3, 2, 4
1, 5, 3, 2, 4
]

i = 2
[
1, 5, 3, 2, 4
1, 5, 2, 3, 4
1, 2, 5, 3, 4
]

i = 3
[
1, 2, 5, 3, 4
1, 2, 3, 5, 4
]

i = 4
[
1, 2, 3, 4, 5
]

swapped变量的作用是：当初始要排序的数列已经是有序的时候，只遍历一遍数列，就退出遍历循环

3.算法特性
稳定的
空间复杂度O(1)
时间复杂度:比较和交换的操作次数，O(n^2)

4.总结
冒泡排序和插入排序有很多相似的地方。但是比插入排序有稍多的开销。