第二章 算法設計思想

一、搜索排序

1.排序算法

https://visualgo.net/zh/sorting

(1)冒泡排序

# 思路：
# (1)比較相鄰元素，如果第一個比第二個大，則交換他們
# (2)第一輪下來，可以保證最后一個數一定是最大的；第二輪下來，可以保證倒數第二個數一定是第二大的。
# (3)執行n-1輪，可以完成排序。
# 比較n-1次？用[3,2,1]冒泡排序后只需要比較2次。
def bubleSort(arr):for j in range(len(arr) - 1):for i in range(len(arr) - 1):if arr[i] > arr[i+1]:temp = arr[i]arr[i] = arr[i + 1]arr[i + 1] = temparr = [5, 4, 3, 2, 1]
bubleSort(arr)
print(arr)

(2)選擇排序

# 思路：
# (1)找到數組中的最小值，選中它并將其放置在第一位 → 經過第一輪交換，第一個值肯定是最小的。
# (2)接著找到第二小的值，選中必將其放置在第二位 → 經過第二輪交換，第二個值肯定是第二小的。
# 以此類推，交換n-1輪def selectionSort(arr):for i in range(len(arr) - 1):indexMin = ifor j in range(i, len(arr)):if arr[j] < arr[indexMin]:indexMin = jtemp = arr[i]arr[i] = arr[indexMin]arr[indexMin] = temparr = [2, 3, 1] # 最壞的情況
selectionSort(arr)
print(arr)

2.搜索算法

http://data.biancheng.net/view/336.html

# 二分插入
# 為什么更新左邊界需+1，但是更新右邊界卻不需要+1？
# 使用了左閉右開的搜索區間，即[l, r)。這意味著左邊界l是包含在搜索區間內的，而右邊界r是不包含在搜索區間內的。所以，當更新左邊界l時，需要加1，因為已經排除了中間元素，而當你更新右邊界r時，這不需要加1，因為要保持右邊界不包含在搜索區間內。這樣做的好處是，當搜索區間為空時，l和r會相等，而且l就是目標元素應該插入的位置。
# 二分查找：從列表中查找元素下標
def binaryInsertIndex(arr, ele):if ele not in arr:return -1l = 0r = len(arr) - 1while l < r:mid = (l + r) // 2if ele < arr[mid]:r = midelse:l = mid + 1 # ele不小于arr[mid]，意味著ele >= arr[mid]，所以需加上1。return larr = [2,3,6,7]
element = 3
arr.insert(binaryInsertIndex(arr, element), element)
print(arr)