一. 清單查詢
"""
要求：從清單中查詢指定元素
輸入：清單，待查詢元素
輸出：元素下标或未查找到元素
方法：
1. 順序查找
2. 二分查找(清單為升序)
""" # 順序查找
def linear_search(data_set, value):
for i in range(len(data_set)):
if data_set[i] == value:
return i
return
print(linear_search([12, 3, 4, 5, 3, 6, 7], 3)) # 二分查找
def bin_search(data_set, value):
left = 0
right = len(data_set) - 1
while left <= right:
mid = (left + right) // 2
if data_set[mid] == value:
return mid
elif data_set[mid] > value:
right = mid - 1
elif data_set[mid] < value:
left = mid + 1
print(bin_search(sorted([12, 3, 4, 5, 3, 6, 7]), 3)) # 二分查找(遞歸版)
def bin_search_rec(data_set, value, left, right):
if left <= right:
mid = (left + right) // 2
if data_set[mid] == value:
return mid
elif data_set[mid] > value:
return bin_search_rec(data_set, value, left, mid - 1)
elif data_set[mid] < value:
return bin_search_rec(data_set, value, mid + 1, right)
print(bin_search_rec(sorted([12, 3, 4, 5, 3, 6, 7]), 3, 0, 6)) 二、清單排序
參考部落格：http://blog.csdn.net/mrlevo520/article/details/77829204
"""
方法：
1. 冒泡排序 （穩定）
2. 選擇排序
3. 插入排序 （穩定）
4. 快速排序
5. 堆排序
6. 歸并排序 （穩定）
7. 希爾排序
""" 
# #################################### 計時裝飾器 ####################################
import time
def cal_time(func):
def wrapper(*args, **kwargs):
t1 = time.time()
result = func(*args, **kwargs)
t2 = time.time()
print("%s running time: %s secs." % (func.__name__, t2 - t1))
return result
return wrapper 計時器裝飾器
# 1. 冒泡排序
# 原理：從索引為0的位置開始，比較索引0和1的值的大小，索引0的值大，則互換位置。再比較索引1和2的值，一趟下來，最大值換到末尾，再從頭比較。
# i: 趟
# j: 指針位置
# 時間複雜度：O（n2） def bubble_sort(li):
for i in range(len(li) - 1):
for j in range(len(li) - 1 - i):
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
li = [12, 3, 4, 5, 3, 6, 7]
bubble_sort(li)
print(li) # 冒泡優化
# 執行一趟沒有交換，則說明清單有序，結束排序
def bubble_sort_op(li):
for i in range(len(li) - 1):
exchange = False
for j in range(len(li) - 1 - i):
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
exchange = True
if not exchange:
return # 2. 選擇排序
# 原理：從索引位置0開始，與位置1的值比較，記錄較小值的索引，再比較1和2的值，一趟下來講位置0和最小索引的值交換。下一趟從索引1開始比較。
# 關鍵點：無序區，最小值索引
# i：趟
# j：指針
# 時間複雜度：O（n2）
def select_sort(li):
for i in range(len(li) - 1):
min_index = i
for j in range(i + 1, len(li)):
if li[j] < li[min_index]:
min_index = j
if min_index != i:
li[i], li[min_index] = li[min_index], li[i] # 寫法二：注意與冒泡排序的區分，趟數區到最後一位。
def select_sort(li):
for i in range(len(li)):
for j in range(len(li) - i):
if li[i] > li[i + j]:
li[i], li[i + j] = li[i + j], li[i]
li = [12, 3, 4, 5, 3, 6, 7]
select_sort(li)
print(li) # 3. 插入排序
# 原理：是每一步都将一個待排資料按其大小插入到已經排序的資料中的适當位置，直到全部插入完畢。
# 從索引1開始，取值存為一個臨時值與有序區的元素比較，遇到第一個比臨時值大的值，此值的下表為j，将臨時值插入到j的位置，其後面的值依次後移。
# 關鍵點：預設序列中的第0個元素是有序的，插入值後，pop出原來的值
# i：趟
# j：指針
# 時間複雜度：O（n2）
def insert_sort(li):
for i in range(1, len(li)):
for j in range(i):
if li[i] < li[j]:
li.insert(j, li[i]) # 首先碰到第一個比自己大的數字，趕緊刹車，停在那，是以選擇insert
li.pop(i + 1) # 因為前面的insert操作，是以後面位數+1，這個位置的數已經insert到前面去了，是以pop彈出
break
li = [12, 3, 4, 5, 3, 6, 7]
insert_sort(li)
print(li) # 4. 快速排序
# 原理：從數列中取出一個值，區分過程，将比這個值大的放在它的右邊，将比這個值小的放在它的左邊，再最左右兩個區域重複這個過程，直到各個區域隻有一個數。
# 時間複雜度：O(nlogn)
# 最壞的情況：每次的取值為最大值或最小值，造成分區不均勻。性能解決插入排序，時間複雜度為O(n2)。
# pivot:樞
def quick_sort(li):
if len(li) < 2:
return li
else:
pivot = li[0]
less = [i for i in li[1:] if i < pivot]
greater = [j for j in li[1:] if j > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
print(quick_sort([1, 5, 2, 6, 9, 3])) # 5. 堆排序
# 堆是一棵順序存儲的完全二叉樹。
# 其中每個結點的關鍵字都不大于其孩子結點的關鍵字，這樣的堆稱為小根堆。
# 其中每個結點的關鍵字都不小于其孩子結點的關鍵字，這樣的堆稱為大根堆。
# 原理：
# 1. 多次調整建立堆，得到堆頂為最大元素
# 2. 取出堆頂，将最後一個元素放到堆頂，經過一次調整重新變成堆。
# 3. 重複建堆，取堆頂元素。
# 時間複雜度：O(nlogn)
def sift(li, left, right):
i = left
j = 2 * i + 1
tmp = li[i]
while j <= right:
if j + 1 <= right and li[j] < li[j + 1]:
j = j + 1
if tmp < li[j]:
li[i] = li[j]
i = j
j = 2 * i + 1
else:
break
li[i] = tmp
def heap_sort(li):
n = len(li)
for i in range(n // 2 - 1, -1, -1): # 建立堆
sift(li, i, n - 1)
for i in range(n - 1, -1, -1): # 挨個出數
li[0], li[i] = li[i], li[0]
sift(li, 0, i - 1)
li = [6, 8, 1, 9, 3, 0, 7, 2, 4, 5]
heap_sort(li)
print(li) # 6.歸并排序
# 原理：用分割的方法将序列分割成一個個已經排好序的序列，再利用歸并的方法将一個個子序列合并成排序好的序列。
# 關鍵點：遞歸分解，歸并
# 時間複雜度：O(nlogn)
def merge(left, right):
result = []
while left and right:
result.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
# if left:
# result.extend(left)
# if right:
# result.extend(right)
return result
def merge_sort(li):
if len(li) <= 1:
return li
mid_index = len(li) // 2
left = merge_sort(li[:mid_index]) # 遞歸拆解的過程
right = merge_sort(li[mid_index:])
return merge(left, right) # 合并的過程
print(merge_sort([1, 5, 2, 6, 9, 3])) # 一般情況下，就運作時間而言：
# 快速排序 < 歸并排序 < 堆排序
# 三種排序算法的缺點：
# 快速排序：極端情況下排序效率低
# 歸并排序：需要額外的記憶體開銷
# 堆排序：在快的排序算法中相對較慢
# 7. 希爾排序
# 原理：一種分組插入排序算法。每次按照gap間隔的分組，對每組進行插入排序。
# 關鍵點：gap——間隙
# 時間複雜度：O((1+τ)n) ≈≈ O(1.3n)
def shell_sort(li):
n = len(li)
gap = n // 2 # 初始步長
while gap > 0:
for i in range(gap, n):
temp = li[i] # 每個步長進行插入排序
j = i - gap
# 插入排序
while j >= 0 and li[j] > temp:
li[j + gap] = li[j]
j -= gap
li[j + gap] = temp
gap = gap // 2 # 得到新的步長
return li
print(shell_sort([1, 5, 2, 6, 9, 3]))