数据结构-学习笔记-冒泡排序

冒泡排序

  • 列表每两个相邻的书,如果前面的数比后面的大,则交换这两个数
  • 一趟排序后,则无序区减少一个数,有序区增加一个数
  • 趟数,无序区,指针的位置
  • 时间复杂度 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]

上一篇:PTA比较大小


下一篇:冒泡排序(Bubble Sort)