一、思維導圖
二、冒泡排序
def bubble_sort(ls):"""用i循環,逐步比較相鄰元素,直到循環結束,停止交換，就像一個個氣泡從下往上冒泡,每一次的循環結果都是最大的元素到了后面已排序序列的列首。"""j = 0 # 用于確定循環次數,同時用于下面排除已排序序列while j < len(ls):i = 0 # 用于遍歷未排序序列while i < len(ls) - 1 - j: # -j排除已排序序列# 兩兩比較if ls[i] > ls[i + 1]:ls[i], ls[i + 1] = ls[i + 1], ls[i]i += 1j += 1
三、選擇排序
def selection_sort(ls):"""選擇排序逐步找到每個最小元素依次放入前面已排序列列尾"""i = 0 # 用于確定遍歷次數，也可理解為已排好序的元素后的第一個位置while i < len(ls) - 1:m = i # 用于存放下標最小值,每次循環前需要重置為i,一次循環結束后交換m和j的位置j = i + 1 # 用于 遍歷i后面的所有元素與i對比，同時把遍歷到的最小值賦值給m，# 遍歷j用于尋找最小的元素并用m標記while j < len(ls):if ls[j] < ls[m]:m = jj += 1if m != i: # 避免無意義的交換ls[i], ls[m] = ls[m], ls[i] # 將尋找到的最小元素交換到最前面i += 1
四、直接插入排序
def insertion_sort(ls):"""直接插入排序"""i = 1 # 記錄待排序列中的第一個元素,從1開始是因為第一步只插入了一個元素沒必要排序while i < len(ls):temp = ls[i] # 用于保存當前元素的值j = i # j用于向前遍歷,逐步與temp比較,若j-1大于temp直接右移j-1,最后當j-1<=temp,空出來的位置填入temp# j<0表示只有一個元素時不必排序while temp < ls[j - 1] and j > 0:ls[j] = ls[j - 1]j -= 1ls[j] = tempi += 1
五、快速排序
def quick_sort_part(ls, L, R):"""快速排序"""# 定義基準P = ls[L]while R > L:while ls[R] >= P and R > L: # R和L是會變化的,所以內循環也要檢查 R 是否 > LR -= 1ls[L] = ls[R] # 比基準小的數據放在左邊while ls[L] <= P and R > L:L += 1ls[R] = ls[L] # 比基準大的數據放在右邊# 當L=R說明只剩最后一個元素，把P填進去ls[L] = P # or ls[R] = Preturn R # 返回當前基準,也可以return Ldef quick_sort(ls, L, R):"""快速排序"""if R > L: # 只有當不止一個元素時才進行快排# 進行第一次快排P_index = quick_sort_part(ls, L, R)# 遞歸,直到R>L# 對基準左邊的進行快排quick_sort(ls, L, P_index - 1) # 此處遞歸結束表示第一次快排之后的左邊部分已經排序完畢。# 對基準右邊的進行快排quick_sort(ls, P_index + 1, R) # 此處遞歸結束表示第一次快排之后的右邊部分已經排序完畢。
六、希爾排序
def shell_sort(ls):""""""n = len(ls) # ls的長度gap = n // 2 # 初始化gap# 確定外層循環次數while gap > 0:for i in range(gap, n): # 從與第一個元素相隔gap的元素開始遍歷j = i # 不能改變外循環的i，需要創建一個j用于比較while j >= gap and ls[j] < ls[j - gap]: # j>=gap 判斷 j-gap 是否會越界。ls[j]<ls[j-gap] 判斷是否需要交換ls[j - gap], ls[j] = ls[j], ls[j - gap] # 交換j -= gap # 讓當前元素繼續向前跳躍 gap 步，去和更前面的同組元素比較，直到它到達正確的插入位置。# 更新步長gap = gap // 2
七、歸并排序
# 定義歸并排序算法
def merge_sort(alist):"""歸并排序"""# 如果列表的元素個數小于等于1 直接返回if len(alist) <= 1:return alist# 將列表從中間分割成兩半mid = len(alist) // 2left_half = alist[:mid]right_half = alist[mid:]# 分別 遞歸 將左右兩部分再次進行分割兩半"""遞歸流程： 直到滿足if len(alist) <= 1:之前會一直遞歸,無法執行到merge函數,滿足if len(alist) <= 1:,之后left_half和right_half會被賦值,兩個都是只有一個元素的列表此時才能執行到合并函數merge,執行完之后會向遞歸的上一層的left_half或right_half返回合并后的列表，此時的left_half和right_half的某一個或者全部會變成兩個元素的列表然后回再次執行合并函數merge,直到整個遞歸流程結束，left_half和right_half為最初分開的兩半,最后執行合并函數即完成整體合并"""left_half = merge_sort(left_half)right_half = merge_sort(right_half)# 合并左右兩部分的序列return merge(left_half,right_half) # 合并# 定義合并的算法
def merge(left,right):"""用于merge_sort遞歸合并的簡單的合并并排序算法"""# 將排序好的額元素放入空列表中arr = []i=0 # 遍歷左邊列表中的每個元素j=0 # 遍歷右邊列表中的每個元素#比較兩個列表中的元素 將小的元素先放入arr空列表中while i<len(left) and j<len(right):if left[i] < right[j]:arr.append(left[i])i+=1else:arr.append(right[j])j+=1# 如果右邊列表由剩余元素 將它直接插入列表中while j<len(right):arr.append(right[j])j+=1# 如果左邊列表由剩余元素 將它直接插入列表中while i < len(left):arr.append(left[i])i += 1return arr
八、二分查找
def binary_search_iter(arr, target):"""在 有序 升序 數組 arr 中查找 target。返回其索引；若不存在返回 -1。"""left, right = 0, len(arr) - 1 # 閉區間 [left, right]while left <= right: # 區間非空mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1 # 去右半邊else:right = mid - 1 # 去左半邊return -1ls = [1, 2, 5, 7, 9, 11, 13, 17, 19, 20]
print(binary_search_iter(ls, 9))
