---

title: 算法導論總復習
author: Clint_chan
categories: [ 陳定鋼]
image: assets/images/flag1.jpg
tags: 算法導論復習,向高分前進！

---

目錄

• 一.排序算法
  • 1.選擇排序
    • 1.1原理&圖示
    • 1.2代碼部分
  • 2.插入排序
    • 2.1原理&圖示
    • 2.2代碼部分
  • 3.歸并排序
    • 3.1原理&圖示
    • 3.2代碼部分
  • 4.快速排序
    • 4.1原理&圖示
    • 4.2代碼部分
  • 5.堆排序
    • 5.1原理&圖示
    • 5.2代碼部分
  • 6.計數排序
    • 6.1原理&圖示
    • 6.2代碼部分
  • 7.桶排序
    • 7.1原理&圖示
    • 7.2代碼部分
  • 8.基數排序
    • 8.1原理&圖示
    • 8.2代碼部分
  • 9.希爾排序
    • 9.1原理&圖示
    • 9.2代碼部分
  • 10.排序算法比較
• 二.紅黑樹
  • 1.紅黑樹定義和性質
• 三.動態規劃
  • 1.鋼條問題
  • 2.矩陣鏈問題
  • 3.LCS問題
• 四.貪心算法
• 五.圖算法
• 六.粒子群算法
• 七.遺傳算法與模擬退火
• 考試資料
• 教案
• 參考文獻

一.排序算法

1.選擇排序

1.1原理及圖示

在未排序數組中找到最小（大）關鍵詞元素排在已排序序列初始位置，再如此，將選中的元素插入到已排序序列末尾。（類似于數據結構的進棧操作）
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-BcGWZJJ7-1608866355870)(https://clint-chan.github.io/CDG/assets/images/selectionSort.gif)]

1.2代碼部分

#Python代碼 def selectionSort(arr):for i in range(len(arr) - 1):# 記錄最小數的索引minIndex = ifor j in range(i + 1, len(arr)):if arr[j] < arr[minIndex]:minIndex = j# i 不是最小數時，將 i 和最小數進行交換if i != minIndex:arr[i], arr[minIndex] = arr[minIndex], arr[i]return arr

2.插入排序

2.1原理及圖示

將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列，依次讀取未排序序列中的元素，并插入到已排序序列合理位置。
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-QUPM9WxK-1608866355874)(https://www.runoob.com/wp-content/uploads/2019/03/insertionSort.gif)]

2.2代碼部分

# Python代碼 def insertionSort(arr):for i in range(len(arr)):preIndex = i-1current = arr[i]while preIndex >= 0 and arr[preIndex] > current:arr[preIndex+1] = arr[preIndex]preIndex-=1arr[preIndex+1] = currentreturn arr

3.歸并排序

3.1原理及圖示

需要申請內存空間，采用遞歸函數，依次二分，直至只剩一個元素，再依次合并。（最底層合并是1合1等于2，倒數第二層是2合2=4）
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-H68KPxkA-1608866355876)(https://www.runoob.com/wp-content/uploads/2019/03/mergeSort.gif)]

3.2代碼部分

# Python代碼 def mergeSort(arr):import mathif(len(arr)<2):return arrmiddle = math.floor(len(arr)/2)left, right = arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))def merge(left,right):result = []while left and right:if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0));while left:result.append(left.pop(0))while right:result.append(right.pop(0));return result

4.快速排序

4.1原理及圖示

從序列中挑選一個基準值作為分割標準，然后再已分割的兩個序列繼續分割，再…分割，最后遞歸地（recursive）合并。如果還不明白請參考更多資料，考試可能要考。
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-TQFhCVOA-1608866355882)(https://www.runoob.com/wp-content/uploads/2019/03/quickSort.gif)]

4.2代碼部分

#快速排序Python代碼 def quickSort(arr, left=None, right=None):left = 0 if not isinstance(left,(int, float)) else leftright = len(arr)-1 if not isinstance(right,(int, float)) else rightif left < right:partitionIndex = partition(arr, left, right)quickSort(arr, left, partitionIndex-1)quickSort(arr, partitionIndex+1, right)return arrdef partition(arr, left, right):pivot = leftindex = pivot+1i = indexwhile i <= right:if arr[i] < arr[pivot]:swap(arr, i, index)index+=1i+=1swap(arr,pivot,index-1)return index-1def swap(arr, i, j):arr[i], arr[j] = arr[j], arr[i]

5.堆排序

5.1原理及圖示

首先構建樹結構，隨后構建極大（小）堆，然后將最后節點與根節點交換，并將該根節點依次取出。
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-JlpVMDHc-1608866355890)(https://www.runoob.com/wp-content/uploads/2019/03/heapSort.gif)]

---

本次期末考試如無特別說明，高度深度從0開始記。

樹的高度為根節點的高度；某節點的高度等于該節點到葉子節點的最長路徑（邊數）；節點的深度是根節點到這個節點所經歷的邊的個數。
構建極大堆時間復雜度:O(lgn)

---

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-6WvsGyb0-1608866355892)(https://clint-chan.github.io/CDG/assets/images/heap-sort.png)]

5.2代碼部分

#堆排序 Python代碼 def buildMaxHeap(arr):import mathfor i in range(math.floor(len(arr)/2),-1,-1):heapify(arr,i)def heapify(arr, i):left = 2*i+1right = 2*i+2largest = iif left < arrLen and arr[left] > arr[largest]:largest = leftif right < arrLen and arr[right] > arr[largest]:largest = rightif largest != i:swap(arr, i, largest)heapify(arr, largest)def swap(arr, i, j):arr[i], arr[j] = arr[j], arr[i]def heapSort(arr):global arrLenarrLen = len(arr)buildMaxHeap(arr)for i in range(len(arr)-1,0,-1):swap(arr,0,i)arrLen -=1heapify(arr, 0)return arr

6.計數排序

6.1原理及圖示

原理的話看圖很好理解；

• （1）找出待排序的數組中最大和最小的元素
• （2）統計數組中每個值為i的元素出現的次數，存入數組C的第i項
• （3）對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
• （4）反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

---

6.2代碼部分

#計數排序Python代碼 def countingSort(arr, maxValue):bucketLen = maxValue+1bucket = [0]*bucketLensortedIndex =0arrLen = len(arr)for i in range(arrLen):if not bucket[arr[i]]:bucket[arr[i]]=0bucket[arr[i]]+=1for j in range(bucketLen):while bucket[j]>0:arr[sortedIndex] = jsortedIndex+=1bucket[j]-=1return arr

7.桶排序

桶排序是計數排序的升級版（將離散數值升級為連續區間）。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：

• 在額外空間充足的情況下，盡量增大桶的數量
• 使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中
• 同時，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關重要。
  理想情況：當輸入的數據可以均勻的分配到每一個桶中。
  最壞情況：所有數據分入一個桶中。

7.1原理及圖示

7.2代碼部分

#桶排序Python代碼 def bucketSort(nums):#選擇一個最大的數max_num = max(nums)# 創建一個元素全是0的列表, 當做桶bucket = [0]*(max_num+1)# 把所有元素放入桶中, 即把對應元素個數加一for i in nums:print(f"{bucket=}")bucket[i] += 1# 存儲排序好的元素sort_nums = []print(f"{bucket=}")for j in range(len(bucket)):n = bucket[j]if n != 0:for _ in range(n):print(f"{sort_nums=}{j=}")sort_nums.append(j)return sort_numsnums = [5,6,3,2,1,65,2,0,8,0,9] print("測試結果:") print(bucketSort(nums))

8.基數排序

8.1原理及圖示

基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。

• 基數排序 vs 計數排序 vs 桶排序
  • 基數排序：根據鍵值的每位數字來分配桶；
  • 計數排序：每個桶只存儲單一鍵值；
  • 桶排序：每個桶存儲一定范圍的數值；

---

8.2代碼部分

#基數排序Python代碼 def radix_sort(s):"""基數排序"""i = 0 # 記錄當前正在排拿一位，最低位為1max_num = max(s) # 最大值j = len(str(max_num)) # 記錄最大值的位數while i < j:bucket_list =[[] for _ in range(10)] #初始化桶數組for x in s:bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶數組print(bucket_list)s.clear()for x in bucket_list: # 放回原序列for y in x:s.append(y)i += 1if __name__ == '__main__':a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]radix_sort(a)print(a)

9.希爾排序

9.1原理及圖示

基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。

由基本思想可以得出希爾排序也就是升級版的插入排序，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

---

9.2代碼部分

#Python代碼 def shellSort(arr):import mathgap=1while(gap < len(arr)/3):gap = gap*3+1while gap > 0:for i in range(gap,len(arr)):temp = arr[i]j = i-gapwhile j >=0 and arr[j] > temp:arr[j+gap]=arr[j]j-=gaparr[j+gap] = tempgap = math.floor(gap/3)return arr

10.排序算法比較

Congretulations! 恭喜你已經復習完了排序算法，下面咱們來比較這些算法吧！

• 穩定性：有隨機性的都統一為不穩定，其余為穩定。
• 空間復雜度：精通流程就可以聯想到。
• 時間復雜度：需要熟讀（偽）代碼并了解數學推導
• In-place & Out-place：需不需要開辟輔助空間

---

二.紅黑樹

1.紅黑樹定義和性質

紅黑樹是一種含有紅黑結點并能自平衡的二叉查找樹。它必須滿足下面性質：

• 性質1：每個節點要么是黑色，要么是紅色。
• 性質2：根節點是黑色。
• 性質3：每個葉子節點（NIL）是黑色。
• 性質4：每個紅色結點的兩個子結點一定都是黑色。
• 性質5：任意一結點到每個葉子結點的路徑都包含數量相同的黑結點。
  • 性質5.1：如果一個結點存在黑子結點，那么該結點肯定有兩個子結點

---

一顆簡單的紅黑樹：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-GcfvauQy-1608866355905)(https://clint-chan.github.io/CDG/assets/images/紅黑樹1.png)]

紅黑樹能自平衡，它靠的是什么？三種操作：左旋、右旋和變色。

• 左旋：以某個結點作為支點(旋轉結點)，其右子結點變為旋轉結點的父結點，右子結點的左子結點變為旋轉結點的右子結點，左子結點保持不變。如圖3。
• 右旋：以某個結點作為支點(旋轉結點)，其左子結點變為旋轉結點的父結點，左子結點的右子結點變為旋轉結點的左子結點，右子結點保持不變。
• 變色：結點的顏色由紅變黑或由黑變紅。

---

插入和刪除相對復雜，需要仔細學習教案和參考資料。

• 插入：插入一共有八種情景；

• 刪除：刪除簡化后仍有九種情景。

點擊這里回到目錄

三.動態規劃

動態規劃三要素：（1）問題的階段（2）每個階段的狀態（3）相鄰兩個階段之間的遞推關系 特點：（1）最優化原理（2）無后效性（3）有重疊子問題 關鍵詞：（1）自底向上（2）填表法（3）寧死不用遞歸 掌握關鍵： 動態規劃不是具體算法，它只是一種思想，要深入理解這種思想。（1）以大化小，把大問題化成小問題，而小問題的解已經存入在某個數據結構當中了，即可以做到調用。（2）調用完即可算出當前需算的結果，然后將此結果當做已知，繼續向頂進行。（3）應用：a.鋼條切割問題中，以大化小，比如要算長度d=4的最優價格，先由d=1算起；那么d_4=max（所有已知結果中最優的組合)，即遍歷操作。①分成兩段，第一段為1，那么第二段為3，而d=3時的最優價格已算出 ，那么①操作就是備選的d_4之一。②...，第一段為2，那么第二段為2，而d=2時的最優價格也已經算出，那么②操作也是備選d_4之一。③...，第一段為3，那么第二段為1，而d=3時的最優價格也已經算出，那么③操作也是備選d_4之一。④...，第一段為4，那么第二段為0，由價格表直接查出價格，也是備選d_4之一。⑤選出最好的d_4。b.LCS問題中，采用動態規劃的具體思想體現在，他每一步都保存了進度，比如我算出長度為4是因為我發現從長度為3開始有新的可行路徑，而不是算每一個長度都從零開始，但依舊是自底向上。我們也可以由此看出，動態規劃無論如何怎樣變，以此衍生的各種算法不變的只有自底向頂的進行計算操作。

---

1.鋼條切割問題

• ①自頂向下（非多項式級復雜度）
• ②帶備忘錄的自頂向下（平方階）
• ③自底向上（平方階）

①自頂向下

#自頂向下 1 def CutRod(p, n): # 函數返回：切割長度為 n 的鋼條所得的最大收益 2 if n == 0: 3 return 0 4 q = -1 5 for i in range(1, n+1): 6 q = max(q, p[i] + CutRod(p, n-i)) 7 return q

Core part:Line 5,6.Specific codes go looking up pdf.

②帶備忘錄的自頂向下

#帶備忘錄的自頂向下 1 def MemorizedCutRod(p, n): 2 r=[-1]*(n+1) # 數組初始化 3 def MemorizedCutRodAux(p, n, r): 4 if r[n] >= 0: 5 return r[n] 6 q = -1 7 if n == 0: 8 q = 0 9 else: 10 for i in range(1, n + 1): 11 q = max(q, p[i] + MemorizedCutRodAux(p, n - i, r)) 12 r[n] = q 13 return q 14 return MemorizedCutRodAux(p, n, r),r

Core part:Line 3,4,5.Specific codes go looking up pdf.

③自底向上

1 def BottomUpCutRod(p, n): 2 r = [0]*(n+1) 3 for i in range(1, n+1): 4 if n == 0: 5 return 0 6 q =0 7 for j in range(1, i+1): 8 q = max(q, p[j]+r[i-j]) 9 r[i] = q 10 return r[n],r

Core part:Line All.Specific codes go looking up pdf.

2.矩陣鏈問題

Python代碼 p = [30, 35, 15, 5, 10, 20, 25] def matrix_chain_order(p):n = len(p) - 1 # 矩陣個數m = [[0 for i in range(n)] for j in range(n)] s = [[0 for i in range(n)] for j in range(n)] # 用來記錄最優解的括號位置for l in range(1, n): # 控制列，從左往右for i in range(l-1, -1, -1): # 控制行,從下往上m[i][l] = float('inf') # 保存要填充格子的最優值for k in range(i, l): # 控制分割點q = m[i][k] + m[k+1][l] + p[i]*p[k+1]*p[l+1]if q < m[i][l]:m[i][l] = qs[i][l] = kreturn m, sdef print_option_parens(s, i, j):if i == j:print('A'+str(i+1), end='')else:print('(', end='')print_option_parens(s, i, s[i][j])print_option_parens(s, s[i][j]+1, j)print(')', end='')r, s = matrix_chain_order(p) print_option_parens(s, 0, 5) 計算次序對計算性能的影響：假設n=3，A1，A2，A3的維數分別為10×100，100×5，5×50。考察A1×A2×A3需要的數乘次數，有以下 兩種計算方式： （1）（A1×A2）×A3：10×100×5+10×5×50=7500 （2） A1×（A2×A3）：100×5×50+10×100×50=75000通過這個簡單的例子足以說明，矩陣的計算次序對計算性能的影響極大。

①所謂標量乘法就是進行了多少次數與數之間的乘法。
②矩陣A 的行列數分別為i,j ；矩陣B的行列數分別為k,l,那么要進行矩陣乘法A·B需首先需滿足j=k（前列等于后行）.
③我們這邊取標量乘法次數為:count=j*k*l.

其中l為第二個矩陣的列數代表要做幾次矩陣乘法（每次矩陣乘法進行了j*k次標量乘法）

④將各數組的行列值分別儲存在指定的數據結構中

3.LCS問題

#Python代碼 import pandas as pd def LCS(s1, s2):size1 = len(s1) + 1size2 = len(s2) + 1# 程序多加一行，一列，方便后面代碼編寫chess = [[["", 0] for j in list(range(size2))] for i in list(range(size1))]for i in list(range(1, size1)):chess[i][0][0] = s1[i - 1]for j in list(range(1, size2)):chess[0][j][0] = s2[j - 1]print("初始化數據：")display(pd.DataFrame(chess))for i in list(range(1, size1)): #讓第一行和第一列為0for j in list(range(1, size2)):if s1[i - 1] == s2[j - 1]: #判斷字符是否相等 如果不相等進入下一個判斷條件chess[i][j] = ['↖', chess[i - 1][j - 1][1] + 1]elif chess[i][j - 1][1] > chess[i - 1][j][1]: #因為初始化為0了，所以自底向上的話：幾何上“左邊”必然大于"下方"，所以置‘←’chess[i][j] = ['←', chess[i][j - 1][1]]else:chess[i][j] = ['↑', chess[i - 1][j][1]]print("計算結果：")display(pd.DataFrame(chess))i = size1 - 1 #從下往上查找j = size2 - 1s3 = []while i > 0 and j > 0:if chess[i][j][0] == '↖':s3.append(chess[i][0][0])i -= 1j -= 1if chess[i][j][0] == '←':j -= 1if chess[i][j][0] == '↑':i -= 1s3.reverse() #逆序輸出print("最長公共子序列：%s" % ''.join(s3))LCS("abcde", "asdzbd") # 總之本程序就是由底至頂，由行至列，最后逆序輸出。

輸出如圖，這里使用display函數美觀的將其輸出（國內技術人員不常用）
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-rqzveATV-1608866355910)(https://clint-chan.github.io/CDG/assets/images/lcs.png)]

要看懂這個圖，并且要與上述代碼一起看，理解每一步，下面我帶大家來理解一下這個圖： 1.輸入和處理操作本圖應從左至右，從上至下看起；輸出操作反之。 2.輸入：先根據字符串的長度確定矩陣的維度(i+1,j+1)，加1的目的是為了實現一種簡陋的美觀<i class="fas fa-feather-alt"></i>（如果結合pandas可以把這個寫在行列索引里），隨后將第一行列以各字符順序填入，其余行列以(flag,0)初始化，其中flag是指↑，↖，←這三種標記。 3.處理：處理操作有兩層for循環，顯而易見是分別用來控制行列的。先把第一行填滿，再把第二行填滿....直到最后一行（行數為輸入的第一個字符串長度加1），其中每一步都保存上一步的結果，在這個算法中體現在長度上。 從[i,j]=[1,1]看起，根據判斷條件，a.如果s1[i - 1] == s2[j - 1]，那么填入[↖,chess[i - 1][j - 1][1] + 1]，其中chess[i - 1][j - 1][1] + 1是指矩陣中左上的那一個元素所儲存的長度值（儲存在第三維度），再加上1b.如果chess[i][j - 1][1] > chess[i - 1][j][1]，即元素chess[i][j]在矩陣中的左邊元素大于其正上方的元素，則chess[i][j]就為flag值='←'和原長度，組成的嵌套數組，即chess[i][j] = ['←', chess[i][j - 1][1]]c.除了上述條件，一切均給chess[i][j]為['↑',原長度]。d.值得注意的是本處理過程判斷條件的先后一定要注意，肯定是先判斷第一個if，判斷兩個子字符是否相等，要不然會亂套。 4.輸出，從右下至左上開始讀取矩陣元素，最后用reverse函數逆序輸出。至于為什么要反著來讀，因為這樣容易找到"回去"的路。

點擊這里回到目錄

四.貪心算法

點擊這里回到目錄

---

考試資料

• [1] 排序算法選擇題
• [2] （李蕓老師）算法導論第1次作業
• [3] （李蕓老師）算法導論第2次作業
• [4] （李蕓老師）算法導論第3次作業
• [5] （李蕓老師）2020秋期中測試題

教案

• [1] 算法基礎知識
• [2] 函數的增長
• [3] 概率分析與隨機算法
• [4] 分治策略
• [5] 堆排序
• [6] 快速排序
• [7] 線性時間排序、統計量
• [8] 基本數據結構
• [9] 二叉搜索樹
• [10] 紅黑樹
• [11] 動態規劃
• [12] 貪心算法
• [13] 基本的圖算法
• [14] 粒子群優化算法
• [15] 遺傳算法與模擬退火算法

參考文獻

• [1] 快速排序算法——C/C++
• [2] Python實現二叉樹遍歷的遞歸和非遞歸算法
• [3] 求遞歸算法時間復雜度：遞歸樹
• [4] 主方法求解遞歸式
• [5] 30張圖帶你徹底理解紅黑樹
• [6] 常見的八大排序算法的比較和選擇依據
• [7] 各種排序算法總結和比較
• [8] leetcode410:分割數組的最大值_填表法求解動態規劃

溫馨提示：用Ctrl+鼠標左鍵可以創建新窗口打開鏈接以便流暢體驗。

點擊這里回到目錄

總結

以上是生活随笔為你收集整理的算法导论总复习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。