# -*- coding: UTF-8 -*-
import random
def bubble_sort(array):
n = len(array) # 数组array的元素数量
for i in range(n-1): # i表示第几趟遍历数组的无序区,一共要遍历n-1趟
for j in range(n-i-1): # j表示数组无序区最右侧元素的索引
if array[j] > array[j+1]:
tmp = array[j]
array[j] = array[j+1]
array[j+1] = tmp
print('第{}趟: {}'.format(i, array))
return array
# bubble_sort()的升级版本,如果某一趟中没有发生交换,说明已完成冒泡排序,那就不继续后续的操作
def bubble_sort_new(array):
n = len(array) # 数组array的元素数量
for i in range(n-1): # i表示第几趟遍历数组的无序区,一共要遍历n-1趟(从第0趟开始)
is_swap = False # 标志位,如果该趟中发生元素交换,其值为True
for j in range(n-i-1): # j表示数组无序区最右侧元素的索引
if array[j] > array[j+1]:
tmp = array[j]
array[j] = array[j+1]
array[j+1] = tmp
is_swap = True
print('第{}趟: {}'.format(i, array))
if not is_swap: # 如果这一趟中没有发生元素交换,那就跳出循环
break
return array
def main():
random_array = [random.randint(0, 100) for i in range(10)] # 随机定义10个0-100之间的数字
print('random_array: {}'.format(random_array))
sorted_array = bubble_sort_new(random_array)
print('sorted_array: {}'.format(sorted_array))
if __name__ == '__main__':
main()
分析
最坏时间复杂度。
冒泡排序一共走了
n
−
1
n-1
n−1趟,第0趟遍历了
n
−
1
n-1
n−1次,第1趟遍历了
n
−
2
n-2
n−2次,第2趟遍历了
n
−
3
n-3
n−3次,…,第n-2趟遍历了
1
1
1次。
因此,冒泡排序总共遍历了
(
n
−
1
)
+
(
n
−
2
)
+
(
n
−
3
)
+
.
.
.
+
1
=
n
∗
(
n
−
1
)
2
(n-1)+(n-2)+(n-3)+...+1=frac{n*(n-1)}{2}
(n−1)+(n−2)+(n−3)+...+1=2n∗(n−1)
次,所以它的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
如果数组是按照要求已经排好顺序的数组,那么只需要走1趟,遍历 n − 1 n-1 n−1次,所以它的时间复杂度是 O ( n ) O(n) O(n)。
稳定性当两个元素相等时,冒泡排序不会对它们进行交换,因此冒泡排序是稳定的。



