python实现冒泡排序

python实现冒泡排序

1.冒泡排序的核心思想是交换，

2.冒泡排序一趟只确定一个元素，

3.冒泡排序的最好时间复杂度为O(n),通常为O(n^2)

def Bubble_Sort(li):
    for i in range(len(li)-1):##总共执行的趟数
        for j in range(len(li)-1-i):##每一趟需要走过的元素数量
            if li[j]>li[j+1]:##判断大小
                li[j],li[j+1] =li[j+1],li[j]#完成交换




import random
li = list(range(30))
random.shuffle(li)
print(li)
Bubble_Sort(li)
print(li)


[9, 5, 15, 7, 24, 3, 12, 28, 25, 8, 19, 2, 21, 4, 22, 10, 29, 18, 26, 14, 6, 1, 16, 0, 27, 20, 11, 23, 17, 13]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

另外冒泡排序还可以控制无效的遍历，当列表已经有序时，我们可以通过设置变量，让函数提前跳出循环，从而减少函数运行时间，提升效率。

def Bubble_Sort1(li):
    for i in range(len(li)-1):#执行的趟数
        print(li)
        exchange = False###设置检测变量，
        for j in range(len(li)-1-i):
            if li[j] > li[j + 1]:

                li[j],li[j+1] = li[j+1],li[j]

                # print(li)
                exchange = True
        if not exchange:
            return li

       设置一个具体例子来看：

def Bubble_Sort(li):
    # print(li)
    for i in range(len(li)-1):##总共执行的趟数
        print(li)
        for j in range(len(li)-1-i):
            # print(li)
            if li[j]>li[j+1]:
                li[j],li[j+1] =li[j+1],li[j]
    return li
        # print(li)

def Bubble_Sort1(li):
    for i in range(len(li)-1):#执行的趟数
        # print(li)
        exchange = False###设置检测变量，
        for j in range(len(li)-1-i):
            if li[j] > li[j + 1]:

                li[j],li[j+1] = li[j+1],li[j]

                # print(li)
                exchange = True
        print(li)
        if not exchange:
            return li


li = [3,4,5,0,1,2,6,7,8,9]
li1 = [3,4,5,0,1,2,6,7,8,9]
# print(li)
print(Bubble_Sort1(li))
# print(li)


print('+++++++')
print(Bubble_Sort(li1))

得到结果：

[3, 4, 5, 0, 1, 2, 6, 7, 8, 9]
[3, 4, 0, 1, 2, 5, 6, 7, 8, 9]
[3, 0, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+++++++
[3, 4, 5, 0, 1, 2, 6, 7, 8, 9]
[3, 4, 0, 1, 2, 5, 6, 7, 8, 9]
[3, 0, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

这样就不会无谓的循环了，节省运行次数