八大排序算法的Python实现__1__冒泡排序

环境

Python 3.5.2

原理

  • 从头开始比较列表中每两个相邻的元素,如果前者比后者大,则将这两个元素交换
  • 第一遍遍历会将最大的元素放置在最右边,而后继续遍历,依次得出第二大、第三大…第二小的元素
  • [优化]每次遍历时,判断各元素之间的位置是否发生了改变,如果没有改变,则直接结束排序

源码

def bubble_sort(l):
    n = len(l)
    for j in range(n-1):
        # 用于判断此轮遍历过程中各元素之间的位置是否发生了改变
        has_change = False
        for i in range(n-1-j):
            if l[i] > l[i+1]:
                l[i+1], l[i] = l[i], l[i+1]
                has_change = True
        if has_change == False:
            break


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

时间复杂度

  • 最优时间复杂度:O(n)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):稳定

说点什么

  Subscribe  
提醒