2.1 插入排序
概念
插入排序算法
本算法要解决的是排序问题:
输入: n 个数 < a1,a2,...,an>.
输出: 输入序列的一个排列(即重新排序)<a'1,a'2,...,a'n>, 使得 a'1≤a'2≤...≤a'n.
待排序的数也称关键字(key).
以下插入排序算法的伪代码以一个过程的形式给出, 称为 INSERTION-SORT, 它的参数是一个数组 A[1..n], 包含了 n 个待排序的数. A 中元素的个数 n 用 length[A]表示. 输入的各个数字是原地排序的(sorted in place), 意即这些数字就是在数组 A 中进行重新排序的, 在任何时刻, 至多只有其中的常数个数字是存储在数组之外的. 当过程 INSERTION-SORT 执行完毕后, 输入数组 A 中就包含了已排好序的输出序列.
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
在上述伪代码中, 外层 for 循环的每一轮迭代开始, 包含元素 A[1..j-1]子数组是一个已经排好序的数组, 内部 while 循环要做的就是将 A[j-1],A[j-2]A[j-3]等元素依次向右移动一个位置, 直到 A[j]找到适当的位置为止.
循环不变式
循环不变式主要用来帮助我们理解算法的正确性, 对于循环不变式, 必须证明它的三个性质:
初始化: 它在循环的第一轮迭代开始之前, 应该是正确的.
保持: 如果在循环的某一次迭代开始前它是正确的, 那么, 在下一次迭代开始之前, 它也应该保持正确.
终止: 当循环结束时, 不变式给了我们一个有用的性质, 它有助于表明算法是正确的.
伪代码中的约定
1)用 "缩进" 表示程序中的分程序 (程序块) 结构.
2)while ,for, repeat 等循环结构, 和 if, then, else 条件结构与 Pascal 中相同. for 循环后循环计数器的值仍然保持.
3)符号 "?" 表示后面不是是个注释.
4)多重赋值 i←j←e 是将表达式 e 的值赋给变量 i 和 j.
5)变量是局部于给定过程的. 没有显示说明的情况下, 不使用全局变量.
6)数组元素通过 "数组名 [下标]" 的形式访问. 符号 ".." 表示数组的一个取值范围, 例如 A[2..j] 包含了 j-1 个元素 A[2],A[3],...,A[j].
7)复合数据一般组织成对象, 它们由属性 (attribute) 或域 (filed) 所组成. 域的访问时有域名后跟由方括号括住的对象名形式表示. 如, 数组可被看作一个对象, 其属性有 length,length[A]就表示数组中的元素个数. 用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针. 对于某个对象 x 的所有域 f, 赋值 y←x 就使得 f[y]=f[x]. 在赋值 y←x 后, x 和 y 指向同一个对象.
8)参数采用按值传递方式: 被调用的过程会收到参数的一份副本. 如果它对某个参数赋值的话, 主调过程是看不见这一变动的. 当对象被传递时, 实际传递的是一个指向该对象数据的一个指针, 而对象的各个域则不被拷贝.
9)布尔运算符 and 和 or 都有短路能力. 意即, 当求表达式 "x and y" 的值时, 先计算 x 的值. 如果 x 的值为 FALSE, 那么整个表达式的值就不可能为 TRUE, 就无需对 y 求值. 短路运算符允许我们写出如 "x≠NIL and f[x]=y" 这样的表达式, 而不用担心当我们试图在 x 为 NIL 时计算 f[x], 会发生怎样的情况.
10)[个人额外补充] 数组下标通常从 1 开始而非 0."=" 是逻辑运算符, 赋值符号是 "←".
习题解答
2.1-1 以图 2-2 为模型, 说明 INSERTION-SORT 在数组 A=<31, 41, 59, 26, 41, 58 > 上的执行过程.
- 31 [(41)] 59 26 41 58
- 31 41 [(59)] 26 41 58
- () 31 41 59 [26] 41 58
- 26 31 41 () 59 [41] 58
- 26 31 41 41 () 59 [58]
- 26 31 41 41 58 59
2.1-2 重写过程 INSERTION-SORT, 使之按非升序排序.
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
将原代码第五行大于改为小于即可
2.1-3 考虑下面的查找问题:
输入: 一列数 A=<a1,a2,...,an > 和一个值 v.
输出: 下标 i, 是的 v=A[i], 或者当 v 不在 A 中出现时为 NIL.
写出针对这个问题的线性查找的伪代码, 它顺序地扫描整个序列以查找 v. 利用循环不变式正面算法的正确性. 确保所给出的循环不变式满足三个必要的性质.
LINEAR-SEARCH(A, v)
for i ← 1 to length[A]
- doif A[i] = v
- do return i
- return NIL
初始化: 初始化 i 为 1, 从数组第一个元素开始查找.
保持: 每次迭代, 下标增长 1, 顺序查找数组, 满足条件 return 当前下标结束循环, 或者遍历完数组结束循环
终止: 两个 return 语句, 一个在循环体中, 找到复合条件的下标直接返回, 终止循环; 一个是循环计数器 i 达到 length[A]+1 以后结束, 说明没有找到复合条件的 A[i],v 不在 A 中, 正确返回 NIL.
2.1-4 有两个各存放在数组 A 和 B 中的 n 位二进整数, 考虑他们的相加问题. 两个整数的和以二进制形式存放在具有 (n+1) 个元素的数组 C 中. 请给出这个问题的形式化描述, 并写出伪代码.
输入: 存放两个二进制数 a1a2...an 和 b1b2...bn 的数组 A=<a1,a2,...,an > 和 B=<b1,b2,...,bn>
输出: 数组 C=<c1,c2,...,cn > 使得二进制数 c1c2...cn=a1a2...an+b1b2...bn
伪代码:
- Binary-ADD(A,B)
- creat arrays C[0..0n+1]
carry ← 0
for i ← n to 1
do v ← A[i]+B[i]+carry
if v> 1
do carry ← 1
C[i+1] ← v-2
else
do carry ← 0
C[i+1] ← v
C[1] ← carry
return C
来源: http://www.bubuko.com/infodetail-3447304.html