普通冒泡
j 的取值（j += 1）：
第一次冒泡：0~4
第二次冒泡：0~3
第三次冒泡：0~2
第三次冒泡：0~1
第五次冒泡：0
j 的上限可通过 i（从 0 ~ 数组长度的值） 和 ｎ （数组的长度）进行控制：
第一次冒泡：4
第二次冒泡：3
第三次冒泡：2
第三次冒泡：1
第五次冒泡：0
class Sort:
def bubble_sort(self, data):
n = len(data)
for i in range(0, n):
for j in range(0, n - i - 1):
if data[j] > data[j+1]:
tmp = data[j]
data[j] = data[j+1]
data[j+1] = tmp
def test_sort():
data = [3, 5, 4, 1, 2, 6]
a = Sort()
a.bubble_sort(data)
data2 = [1, 2, 3, 4, 5, 6]
assert data == data2
if __name__ == '__main__':
test_sort()
提前退出
利用 flag 提前退出
3, 5, 4, 1, 2, 6
class Sort:
def bubble_sort(self, data):
n = len(data)
flag = False
for i in range(0, n):
for j in range(0, n - i - 1):
if data[j] > data[j+1]:
tmp = data[j]
data[j] = data[j+1]
data[j+1] = tmp
flag = True
if not flag:
break
def test_sort():
data = [3, 5, 4, 1, 2, 6]
a = Sort()
a.bubble_sort(data)
data2 = [1, 2, 3, 4, 5, 6]
assert data == data2
if __name__ == '__main__':
test_sort()
时间复杂度
- 最好：O(n)
- 最坏：O(n2)
- 平均：O(n2)
空间复杂度
O(1)
稳定性
稳定：