冒泡排序法python详解-什么是冒泡法排序

冒泡排序的原理就是反复遍历一个需要排序的数组。 为了方便，通常将这个数组放在一个列表中进行操作。 每次遍历都会比较相邻的两个元素。 如果书的顺序错了，则交换它们（本文中较大的数字放在序列的右边，较小的数字放在左边，即要呈现的结果是即最终的有序排列是从小到大排列）冒泡排序法python详解，重复该操作，直到不需要交换为止。 它是按顺序排列的。 值得注意的是，每次遍历数组时冒泡排序法python详解，数组中最大的数都会放在最右边，所以下次遍历时不需要遍历最大的元素。 因此，每次遍历序列，都取最大的数。

例如：一个待排序的数组

23 34 3 54 43

第一关：

23 34>3 需要交换

序列变为 23 3 34 54 43

34 54>43 交换得到 23 3 34 43 54

至此遍历结束，最右边的数最大

代码如下：

list = [23 34 3 54 43]
for i in range(len(list)-1):
    if list[i] > list[i+1]:
        list[i], list[i+1] = list[i+1], list[i]
#执行上边代码后就会得到新数列23 3 34 43 54

第二次遍历只需要遍历新的序列23 3 34 43

重复第一次遍历的步骤

最终的实现代码如下：

list = [23 34 3 54 43]
for j in range(len(list)-1):
    for i in range(len(list)-1-j):
        if list[i] > list[i+1]:

            list[i], list[i+1] = list[i+1], list[i]

上述算法的时间复杂度为n，其中n为数组元素个数

如果一个数组已经是有序数组，那么第一次遍历就应该知道它是一个有序数组（因为如果是一个有序数组，可以注意到if条件不成立），那么就不需要执行第二次遍历，我们可以更改算法优化

优化后的代码如下：

def bubble_sort(alist):
    """冒泡排序"""
    n = len(alist)

    for j in range(n-1):
        """外层for循环是将次大数字选出来"""
        count = 0
        for i in range(n-1-j):
            """内层for循环是选出这个列表中的最大的数字，同时把这个数字放到列表的最右边"""
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

                count += 1
            if count == 0:
                """已经是有序排列"""
                break
if __name__ == "__main__":
    li = [23 34 3 54 43]
    bubble_sort(li)
    print(li)