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

数据结构与算法(冒泡排序)

程序员文章站 2022-07-08 14:52:26
...

冒泡排序

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把它们交换过来。遍历数列的工作是重复的进行直到没有在需要的交换,也就是说该数列已经排序完成,这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡算法的运作如下:

  • 比较相邻的元素,如果第一个元素大于第二个元素(升序),就交换它们两个。
  • 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这步完成后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个
  • 持续每次越来越少的元素重复上面的步骤,直到没有任何一堆数字需要比较。

冒泡算法分析

交换过程图示(第一次):
数据结构与算法(冒泡排序)
那么我们需要进行n-1次冒泡过程,每次对应的比较次数如下图所示:

Pass Comparisons
1 n-1
2 n-2
3 n-3
n-1 1

代码实现

def bubble_sort(alist):
    """冒泡排序"""
    for j in range(len(alist)-1): 
        for i in range(len(alist)-j-1):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

    return alist

时间复杂度

  • 最优时间复杂度:O(n)表示遍历一次发现没有任何可交换的元素,排序结束
  • 最坏时间复杂度:O(n2)O(n^2)
  • 稳定性:稳定

冒泡复杂度的优化

对于一开始就有序的序列,时间复杂度为O(n)

#优化冒泡算法
def bubble_sort(alist):
    """冒泡排序"""
    for j in range(len(alist)-1): 
        count = 0
        for i in range(len(alist)-j-1):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        if 0 == count:
            return alist
相关标签: 数据结构