Python編程：排序算法之冒泡排序
發(fā)布時(shí)間：2021-11-23 點(diǎn)擊數(shù)：548
列表排序
- 將無(wú)序列表變?yōu)橛行蛄斜?
- 輸入：無(wú)序列表
- 輸出：有序列表
常見(jiàn)的排序算法
|
名稱 |
時(shí)間復(fù)雜度 |
空間復(fù)雜度 |
||||
|
冒泡排序 |
O(n^2) |
O(1) |
||||
|
選擇排序 |
O(n^2) |
O(1) |
||||
|
插入排序 |
O(n^2) |
O(1) |
||||
|
快速排序 |
mid |
|
||||
|
堆排序 |
high |
|||||
|
歸并排序 |
high |
|
||||
|
基數(shù)排序 |
少見(jiàn) |
|
||||
|
希爾排序 |
少見(jiàn) |
|
||||
|
桶排序 |
少見(jiàn) |
|
||||
排序算法關(guān)鍵點(diǎn)：
- 有序區(qū)
- 無(wú)序區(qū)
冒泡排序
- 列表每?jī)蓚€(gè)相鄰的數(shù)，如果前邊的比后邊的大，那么交換這兩個(gè)數(shù)
代碼實(shí)現(xiàn)
import random # 冒泡排序，從小到大排序O(n^2) def bubble_sort(lst): count = 0 n = len(lst) - 1 # 9 總遍歷次數(shù)，比序列總數(shù)少1 for i in range(n): # 0-8 for j in range(n-i): # 8-0 if lst[j]>lst[j+1]: # 前者比后者大則交換 lst[j], lst[j+1] = lst[j+1], lst[j] count += 1 print("count: %s", count) # 冒泡排序改進(jìn)，從小到大排序 def bubble_sort_1(lst): count = 0 n = len(lst) - 1 # 9 總遍歷次數(shù)，比序列總數(shù)少1 for i in range(n): # 0-8 exchange = False for j in range(n-i): # 8-0 if lst[j]>lst[j+1]: # 前者比后者大則交換 lst[j], lst[j+1] = lst[j+1], lst[j] exchange = True count += 1 if exchange==False: # 如果遍歷結(jié)束沒(méi)有任何交換,說(shuō)明已經(jīng)有序 break print("count: %s", count) lst = list(range(10)) # random.shuffle(lst) #打亂順序 bubble_sort(lst) # count: %s 45 bubble_sort_1(lst) # count: %s 9 print(lst) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]