冒泡排序
- 列表每两个相邻的书,如果前面的数比后面的大,则交换这两个数
- 一趟排序后,则无序区减少一个数,有序区增加一个数
- 趟数,无序区,指针的位置
- 时间复杂度 O(n^2)
- i = 0 (第一趟) {j = 0 to n - 1} 左闭右开
- i = 1 (第二趟) {j = 0 to n - 2} 左闭右开
- …
- i (第i+1趟) {j = 0 to n-i-1} 左闭右开
import random
def Bubble_sort(li):
print("排序前: %s"%li)
for i in range(len(li)-1):
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
print("共走了%d趟,排序后: %s"%(i,li))
li = [random.randint(0,100) for i in range(10)]
Bubble_sort(li)
# 排序前: [66, 75, 37, 72, 91, 86, 25, 58, 55, 90]
# 共走了8趟,排序后: [25, 37, 55, 58, 66, 72, 75, 86, 90, 91]
优化
- 如果无序区已有顺序,会重复进行工作
- 如果一趟的过程中没有发生交换,认为无序区已排好顺序
import random
def Bubble_sort(li):
print("排序前: %s"%li)
for i in range(len(li)-1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
print(li)
if not exchange:
print("共走了%d趟,排序后: %s"%(i,li))
return
# li = [random.randint(0,100) for i in range(10)]
li = [9,8,7,6,5,1,2,3,4]
Bubble_sort(li)
# 排序前: [9, 8, 7, 6, 5, 1, 2, 3, 4]
# [8, 7, 6, 5, 1, 2, 3, 4, 9]
# [7, 6, 5, 1, 2, 3, 4, 8, 9]
# [6, 5, 1, 2, 3, 4, 7, 8, 9]
# [5, 1, 2, 3, 4, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 共走了5趟,排序后: [1, 2, 3, 4, 5, 6, 7, 8, 9]