python3实现数据结构与算法30天-排序-冒泡排序(4)

基本思想:

1.列表每两个相邻的数，如果前面的比后面大，则交换这两个数
2.一趟排序完成后，则无序区减少一个数，有序区增加一个数

注意：趟，无序区范围

时间复杂度：O(n^2)

代码实现：

import random

def bubble_sort(lst):
    for i in range(len(lst)-1):

        exchange_flag = False
        for j in range(len(lst)-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                exchange_flag = True
        print(lst)
        if not exchange_flag:
            return

lst=[random.randint(0,100) for x in range(10)]
print(lst)
bubble_sort(lst)

测试结果

[30, 85, 57, 57, 27, 29, 59, 83, 49, 9]
[30, 57, 57, 27, 29, 59, 83, 49, 9, 85]
[30, 57, 27, 29, 57, 59, 49, 9, 83, 85]
[30, 27, 29, 57, 57, 49, 9, 59, 83, 85]
[27, 29, 30, 57, 49, 9, 57, 59, 83, 85]
[27, 29, 30, 49, 9, 57, 57, 59, 83, 85]
[27, 29, 30, 9, 49, 57, 57, 59, 83, 85]
[27, 29, 9, 30, 49, 57, 57, 59, 83, 85]
[27, 9, 29, 30, 49, 57, 57, 59, 83, 85]
[9, 27, 29, 30, 49, 57, 57, 59, 83, 85]