2.1 插入排序

排序问题

输入：n个数的一个序列<a1,a2,……,an>。

输出：输出序列的一个排列<a1',a2',……,an'>，满足a1'≤a2'≤……≤an'。

希望排序的数称为关键词。

伪代码过程 INSERTION-SORT(A)

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

循环不变式与插入排序的正确性

我们将采用这种循环不变式的方法来证明算法的正确性

循环不变式三条性质

初始化：循环的第一次迭代之前，它为真。

保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。

终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

伪代码中的一些约定

A[i] 表示数组A的第i个元素
A[1..j]表示A的一个子数组，它包含j个元素A[1],A[2],……A[j]
..表示数组中值的一个范围
error表示因为已被调用的过程情况不对而出现了一个错误。调用过程负责处理该错误，所以我们不用说明将采取什么行动。

2.3 设计算法

分治模式在每层递归时的三个步骤

分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
合并这些子问题的解成原问题的解。

归并排序

分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。

解决：使用归并排序递归地排序两个子序列。

合并：合并两个已排序的子序列以产生已排序的答案。

伪代码过程MERGE

MERGE(A,p,q,r)
  n1 = q - p + 1//计算子数组A[p..q]的长度n1
  n2 = r - q//计算子数组A[q+1,r]的长度n2
  let L[1..n1+1] and R[1..n2+1]be new arrays//创建长度分别为n1+1和n2+1的数组L和R（“左”和“右”），每个数组中额外的位置将保存哨兵【避免在每个基本步骤必须检查是否有堆为空】
  //将子数组A[p..q]复制到L[1..n1]
  for i = 1 to n1
    L[i] = A[p+i-1]
  //将子数组A[q+1..r]复制到R[1..n2]
  for j = 1 to n2
    R[j] = A[q+j]
  //将哨兵放在数组L和R的末尾
  L[n1+1] = ∞
  R[n2+1] = ∞
  //通过维持循环不变式，执行r-p+1个基本步骤
  i = 1
  j = 1
  for k = p to r
    if L[i] ≤ R[j]
      A[k] = L[i]
      i = i + 1
    else A[k] = R[j]
      j = j + 1

伪代码过程 MERGE-SORT

//为了排序整个序列A=<A[1],A[2],……,A[n]>，我们执行初始调用MERGE-SORT（A,1,A.length）
MERGE-SORT(A,p,r)
  if p < r
    q = {(p+r)/2}///向下取整
    MERGE-SORT(A,p,q)
    MERGE-SORT(A,q+1,r)
    MERGE(A,p,q,r)

2.3-7

Describe a Θ(nlgn)-time algorithm that, given a set S of n integers and another integer x determines whether or not there exist two elements in S whose sum is exactly x.

描述一个运行时间为Θ(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。

Solution

alt

伪代码过程 TWO-SUM(A,x)

TWO-SUM(A,x)
  MERGE-SORT(A,1,A.length)
  i = 1
  j = A.length
  while i < j
    if A[i] + A[j] < x
      i = i + 1
    elseif A[i] + A[j] > x
      j = j - 1
    else
       print "S中存在两个其和刚好为x的元素"
       return
   print "S中不存在两个其和刚好为x的元素"

第2章 算法基础