算法学习（一）

xiaoxiao2021-03-01  15

INSERTION-SORT(A)

1 for j ← 2 to length[A] 2 do key ← A[j] 3 ▹ Insert A[j] into the sorted sequence A[1 ‥ j - 1]. 4 i ← j - 1 5 while i > 0 and A[i] > key 6 do A[i + 1] ← A[i] 7 i ← i - 1 8 A[i + 1] ← key

j从２开始循环，直到整个数组的长度length[A]

（１）i=j-1，当i>0即i有效

（２）A[i]>key，因为从A[1]-A[j-1]（即A[i]）已经是个有序递增的序列，如果key>A[i]则位置不用变，只有key<A[i]时才会准备把key值向前面的位置移动，移动时当A[i]>key时，要先把A[i]放到A[i+1]的位置即A[j]的位置，因为A[j]已经赋给key了，所以不必担心A[j]的丢失，然后光标要向前移一位，即移到i-1的位置，再比较依次类推

Consider the searching problem:

Input: A sequence of n numbers A = a1, a2, . . . , an and a value v.

Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

for i <- 1 to n do if v = A[i] return i end if end for return nul

Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers

k <- 0 for i <- 1 to n do if A[i] + B[i] + k = 3 then C[i] <- 1 k <- 1 else if A[i] + B[i] + k = 2 then C[i] <- 0 k <- 1 else C[i] <- A[i] + B[i] k <- 0 end if end if end for if k = 1 then C[n+1] <- 1 else C[n+1] <- 0 end if