筆記
插入排序是最簡單的一種排序算法哗咆，它的偽代碼如下：
代碼2.1-1：插入排序
// 參數(shù) A：待排序的數(shù)組
INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
// Insert A[j] into the sorted sequence A[1..j-1]
i = j-1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i-1
A[i+1] = key
練習
2.1-1 以圖2-2為模型究抓，說明INSERTION-SORT在數(shù)組上的執(zhí)行過程猾担。
解
2.1-2 重寫過程INSERTION-SORT，使之按非升序（而不是非降序）排序刺下。
解
代碼2.1-2：非升序插入排序
// 參數(shù) A：待排序的數(shù)組
REVERSE-INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
// Insert A[j] into the sorted sequence A[1..j-1]
i = j-1
while i > 0 and A[i] < key
A[i+1] = A[i]
i = i-1
A[i+1] = key
2.1-3 考慮以下查找問題：
輸入：個數(shù)的一個序列
和一個值
绑嘹。
輸出：下標使得
或者當
不在
中出現(xiàn)時，
為特殊值
橘茉。
寫出線性查找的偽代碼工腋，它掃描整個序列來查找。使用一個循環(huán)不變式來證明你的算法是正確的捺癞。確保你的循環(huán)不變式滿足三條必要的性質(zhì)夷蚊。
解
代碼2.1-3：線性查找
// 參數(shù) A：一個數(shù)組
// 參數(shù) v：需要查找的值
LINEAR-SEARCH(A, v)
for i = 1 to A.length
if A[i] == v
return i
return NIL
2.1-4 考慮把兩個位二進制整數(shù)加起來的問題，這兩個整數(shù)分別存儲在兩個
元數(shù)組
和
中髓介。這兩個整數(shù)的和應按二進制形式存儲在一個
元數(shù)組
中。請給出該問題的形式化描述筋现，并寫出偽代碼唐础。
解
代碼2.1-4：二進制整數(shù)相加
// 參數(shù) A和B：表示兩個二進制整數(shù)的數(shù)組，數(shù)組中的元素只能是0或1
// 參數(shù) n：輸入數(shù)組的長度
// 參數(shù) v：需要查找的值
BINARY-ADD(A, B, n)
create a new array C[1..n+1]
carry = 0
for i = 1 to n
sum = A[i] + B[i] + carry
if sum < 2
C[i] = sum
carry = 0
else
C[i] = sum - 2
carry = 1
C[n+1] = carry
代碼鏈接：
https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter02/Section_2.1
