关于各种排序算法的动画演示 https://visualgo.net/zh/sorting?slide=1

  • 冒泡排序
  1. 比对的次数复杂度是O(n^2),交换的时间复杂度也是O(n^2)
  2. 优势：无需额外的存储空间，可以在链表上操作
  3. 原理：比较两个相邻的元素，将值大的元素交换到右边
    def bubbleSort(alist):
 for passnum in range(len(alist)-1,0,-1):
     for i in range(passnum):
         if alist[i] > alist[i+1]:
             alist[i],alist[i+1] = alist[i+1],alist[i]
  • 性能改进：如果某趟比对没有发生任何交换，说明列表已经排好序，可以提前结束算法 
def shortbubbleSort(alist):
    exchanges = True
    passnum = len(alist)-1
    while passnum > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
                exchanges = True
        passnum -= 1

图片说明