排序演算法
排序演算法
介紹五個排序演算法
- 插入排序
- 泡沫排序
- 快速排序
- 選擇排序
- 桶子排序
1.插入排序
(3) ( 2 1 )
(2 3 ) ( 1 )
(1 2 3 )
把排列分成已排好和未排好
左邊括弧是已排好
右邊括弧是未排好
每次都從未排好的第一個數字，向左跟已排好的數字比較
因為每次都是用一個數子去跟已排序的值比較
每次循環能確保已排序的值一定是完成排序的
之所以叫插入排序
估計是需要移動已排序的值，找一個適合的位置把未排序的值插入進去
很像是玩大老二的時候的思考方法
def insert_sort(data):
for i in range(1, len(data)): #從一因為大於兩個數字才需要排序
tmp = data[i]
tmp_idx = i
for j in range(i , 0, -1):
#不包含0因為，loop時 每次都會去和-1的值比較
if tmp < data[j-1]:
data[j] = data[j-1]
tmp_idx = j-1 #取得插入值的索引
data[tmp_idx] = tmp
2.泡沫排序
泡沫排序是兩兩交互的值互相比較
總共loop n-1次，就可以完成排序(註1)
每個loop要要比較 k-1 次(註2) ，因為是兩個比較要-1
註1. n為數值的總數
註2. k為每次loop的索引
(3 2) 1
2 (3 1)
(2 1) 3 <完成一次比較，得到一個排完的數3>
def bubble_sort(data):
for i in range(len(data)-1, 0, -1):
#總共loop 陣列長度-1
for j in range(i, 0, -1):
#從目前陣列索引往索引1比較
tmp = data[j-1]
data[j-1] = data[j]
data[j] = tmp
3.快速排序
快速排序的理念是找一個基準點
小於基準點的放到左邊，大於基準點的放到右邊
然後再繼幫排序完的數列再進行更小範圍的快速排序
直到沒有更小單位的數列為止
(3) 2 1
選3為基準點，選第一或最後都可以，這兩個比較好寫
因為基準點選前面，所以不可以直接從前面找 >= 3
不然會計算失敗
從右邊找 < 3，找到1
從左邊邊找 >= 3，也是找到1
兩值根據基準點交換位置的時候會有兩種狀況
- 找到的索引一樣，代表這是新的基準點，要與目前的基準點互換
- 找到的索引不一樣，兩值交換位置
| 3 | 2 | 1 |
|---|---|---|
| L | ||
| R |
1 2 3
再來要對更小的範圍快速排序
以基準點為中間，左右各切一半
(1 2) (3) ()
(start, L-1) 左邊區塊
(L+1, end) 右邊邊區塊
如果 起點 >= 終點就結束
註1. start為起始索引，end為結束索引
def quick_sort(data, start, end):
if start >= end:
return
base_v = data[start]
L = start
R = end
while L != R:
while L < R and data[R] >= base_v:
# L <= R 比較就沒有意義，而且會讓索引不準確
# L和R最多一樣，不會讓 L > R
R -= 1
while L < R and data[L] <= base_v:
L += 1
if L < R:
# 以基準點為基準 兩邊交換
tmp = data[L]
data[L] = data[R]
data[R] = tmp
#交換基準點
tmp = data[L]
data[L] = base_v
data[start] = tmp
#分段繼續快速排序
quick_sort(data, start, L-1)
quick_sort(data, L+1, end)
4.選擇排序
3 2 1
假定3是最小的，從2向後比較，找到比自己小的
1 (2 3)
就可以確定1是最小的，然後往下一個2，重複此項操作
抓取最小的值要n-1次
互相比較的次數需要 n(n-1)/2
def selection_sort(data):
for i in range(len(data)):
min_v_idx = i
for j in range(i+1, len(data)):
# i基礎點，+1索引與基礎點比較
if data[min_v_idx] > data[j]:
min_v_idx = j
if min_v_idx != i:
tmp = data[i]
data[i] = data[min_v_idx]
data[min_v_idx] = tmp
5.桶子排序
桶子排序的理念是利用空間來完成排序
每個數子都有屬於自己的桶子
3 2 1
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 1 | 1 | 1 |
把 3 2 1 放到桶子裡
然後按照順序，桶子有數值的就輸出值的數量
這是簡單的解釋，實際上使用會難一些
下面的code是引用自維基百科
並修改is_sub_bucket -> bucket_level
減少不必要的loop
加上我自己寫的註解
# 修改is_sub_bucket:bool -> bucket_level:int
# 因為到第三層，桶子的值已經是排好的，不需要再去比大小
def bucket_sort(arr: list, bucket_level: int = 0):
if is_sort(arr, bucket_level):
return
bucket_num: int = max(arr) // 10 + 1 if bucket_level == 0 else 10
# 2種狀況
# 1 大區塊的桶子
# 裡面的數字最大如果有100，拆分100個體積太大
# 所以除以10
# +1 是因為 0~9一組 依此類推，100就需要+1的桶子去裝
# 2 小區塊的桶子
# 大小固定是 10，因為大區塊是 0~9一組
# 小區塊是大區塊再繼續去拆分的
buckets: list[list] = [[] for _ in range(bucket_num)]
for a in arr:
i: int = a // 10 if bucket_level == 0 else a % 10
buckets[i].append(a)
# 以 100 為大區塊為例子
# buckets可能長 [[3,0,9,1,9],[10,12,11,19]....]
# 以 100 為小區塊為例子
# buckets可能長 [[0],[1],[ ],[3],....[9, 9, 9]]
arr.clear()
# 清空目前參考陣列的數值
# 因為等等arr會加入排序好的
# buckets 有儲存未排序的
for bucket in buckets:
bucket_sort(bucket, bucket_level+1)
arr += bucket
# is_sub_bucket:bool -> bucket_level:int
def is_sort(arr: list, bucket_level: int) -> bool:
if bucket_level > 1: #第三層就返回
return True
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
else:
return True