算法学习(一)

xiaoxiao2021-03-01  3

插入排序伪代码:

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从2开始循环,直到整个数组的长度length[A]

(1)i=j-1,当i>0即i有效

(2)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

 

转载请注明原文地址: https://www.6miu.com/read-3850132.html

最新回复(0)