欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

冒泡排序(Python实现)

程序员文章站 2022-03-24 15:44:56
...

冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法

它重复地走访过要排序的元素列,一次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

算法原理

冒泡排序算法的原理如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

  3. 针对所有的元素重复以上的步骤,除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

def bubble_sort(alist):
    for j in range(len(alist)-1):
        for i in range(len(alist)-1-j):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist


if __name__ == '__main__':
    li = [1,3,4,2,9,5,8]
    print(li)
    bubble_sort(li)
    print(li)

思路:若列表有存在n个元素

第1次开始比较的时候经过n-1次的比较将最大的数传到最后

第2次开始比较的时候经过n-2次的比较将第二大的数传到倒数第二个

.......

第N次需要交换(n-N)次

一共需要交换(n-1)次

也可以换成下面这种写法

def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        for i in range(j):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
    return alist

if __name__ == '__main__':
    li = [1,3,4,2,9,5,8]
    print(li)
    bubble_sort(li)
    print(li)

这样的时间复杂度是O(n**2)

但是如果本来的列表顺序就是顺序排列呢?每次仍然需要排列N**2次有点浪费

def bubble_sort(alist):
    for j in range(len(alist)-1):
        count = 0
        for i in range(len(alist)-1-j):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
                count += 1
        if count == 0:
            return alist
    return alist

if __name__ == '__main__':
    li = [1,3,4,2,9,5,8]
    print(li)
    bubble_sort(li)
    print(li)

我们可以设置一个变量,如果走完一轮还没有发现有任何交换过的次数,

说明此时列表是顺序的(最优情况下时间复杂度是O(n))

直接返回即可