01.冒泡排序算法的通俗讲解(Python)

    xiaoxiao2022-07-13  143

    冒泡排序的原理是对一个需要排序的数列进行重复的遍历,为了方便,通常把这个数列放在一个列表进行操作,每遍历一次,比较相邻的两个元素,如果书序错误,就把它们调换(本文把大的那个数放到数列的右边,小的数放左边,即要呈现的结果就是最后的有序排列是按从小到大排列的)重复操作,直到没有需要交换,说明已经是有序排列了。值得注意的是,每遍历一次数列,数列中的最大的那个数就会被放到最右边,那么下一次遍历的时候就不需要再遍历这个最大的元素了。因此,每一次遍历的数列都得到最大的那个数。 举个例子:一个待排序数列 23 34 3 54 43  第一次遍历: 23<34  不需要交换 34>3  需要交换   数列变成了 23 3 34 54 43  34<54不交换  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)

     

    最新回复(0)