最优时间复杂度 O(n) 表示遍历一次发现没有任何可以交换的元素 排序结束。
最坏时间复杂度 O(n2)
稳定性 稳定
#coding utf-8 #冒泡排序 def bubble_sort(alist): 冒泡排序 for j in range(len(alist)-1): count 0 for i in range(0,len(alist)-1-j): #左闭右开 要走到倒数第二个位置 #从头走到尾 if alist[i] alist[i 1]: count 1 alist[i],alist[i 1] alist[i 1],alist[i] if count 0: #哪次过程没有交换了 直接退出 return # i 0 n-2 range(0,n-1) j 0 # i 0 n-3 range(0,n-1-1) j 1 # i 0 n-4 range(0,n-1-2) j 2 # i 0 n-n 1 range(0,n-n 2) j n-2 if __name__ __main__ : li [14,12,5,1,9,3,6,7,8] print(li) bubble_sort(li) print(li) 运行结果: [14, 12, 5, 1, 9, 3, 6, 7, 8] [1, 5, 3, 6, 7, 8, 9, 12, 14]2. 选择排序 时间复杂度
最优时间复杂度 O(n2)
最坏时间复杂度 O(n2)
稳定性 不稳定 考虑升序每次选择最大的情况
#coding utf-8 #选择排序 # alist [54,336,93,17,77,31,44,55,20] def select_sort(alist): 选择排序 n len(alist) for i in range(n-1): mix alist[i] for j in range(i 1,n): if alist[j] mix: mix alist[j] alist[i],alist[k] alist[k],alist[i] k i 1 if __name__ __main__ : alist [54,336,93,17,77,31,44,55,20] print(alist) select_sort(alist) print(alist) 运行结果: [54, 336, 93, 17, 77, 31, 44, 55, 20] [17, 20, 31, 44, 54, 55, 77, 93, 336]3. 插入排序 时间复杂度
最优时间复杂度 O(n) 升序排列 序列已经处于升序状态
最坏时间复杂度 O(n2)
稳定性 稳定
#coding utf-8 #插入排序 def insert_sort(alist): 插入排序 n len(alist) for j in range(1,n): while i 0: if alist[i] alist[i-1]: alist[i],alist[i-1] alist[i-1],alist[i] i i - 1 else: break if __name__ __main__ : alist [54, 336, 93, 17, 77, 31, 44, 55, 20] print(alist) insert_sort(alist) print(alist) 运行结果: [54, 336, 93, 17, 77, 31, 44, 55, 20] [17, 20, 31, 44, 54, 55, 77, 93, 336]
