🌹 喇賽的人 Blog 🌹

🌹 喇低喇賽 🌹

0%

演算法第一堂 插入排序

亂寫於 Disqus：
廢話字數： 717 所需傷眼時間 ≈ 1 分鐘

 

這裡虛擬碼的箭頭 <- 表示程式裡面等於 = 用來賦予變數數值
這裡的 do 沒有任何特殊涵義, 單純表示執行而已
虛擬碼的起始為 1, 所以 for j <- 2 這邊實際上對應到程式語言是 1

1
2
3
4
5
6
7
8
9
insertion-sort(A)
for j <- 2 to length[A]
	do key <- A[j]
		*Insert A[j] into the sorted sequence A[1..j-1]
		i <- j - 1
		while i > 0 and A[i] > key
			do A[i+1] <- A[i]
			i <- i - 1
		A[i+1] <- key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def insertion_sort(A):
    # for j <- 2 to length[A]
    for j in range(1, len(A)): 
        
        # do key <- A[j]
        key = A[j]
        
        # *Insert A[j] into the sorted sequence A[1..j-1]
        # 這行是註解，說明接下來要做的事
        
        # i <- j - 1
        i = j - 1
        
        # while i > 0 and A[i] > key
        # (在 Python 中，索引從 0 開始，所以條件改為 i >= 0)
        while i >= 0 and A[i] > key:
            
            # do A[i+1] <- A[i]
            A[i+1] = A[i]
            
            # i <- i - 1
            i = i - 1
            
        # A[i+1] <- key
        A[i+1] = key

# 測試一下程式碼
data = [5, 2, 4, 6, 1, 3]
insertion_sort(data)
print("排序後的結果：", data)
關閉