<算法导论>学习笔记(2)--第2章算法基础

心已赠人 2022-08-24 14:09 558阅读 0赞

**<算法导论>学习笔记(2)--第2章 算法基础**

Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.

是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。

**1. 循环不变式的三个性质:(循环不变式通常用来证明递归的正确性)**

**1. 初始化:它在循环的第一轮迭代开始之前,应该是正确的。**

**2. 保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。**

**3. 终止:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。**

**2. 伪代码中的约定:**

**1. 书写上的“缩进”表示程序中的分程序(程序块)结构。**

**2. while,for,repeat 等循环结构和 if,then,else 条件结构与 Pascal 中相同。**

**3. 符号 "▷”表示后面部分是个注释。**

**4. 多重赋值 i←j←e 是将表达式 e 的值赋给变量 i 和 j;等价于 j←e,再进行赋值 i←j。**

**5. 变量(如 i,j 和 key 等)是局部给定过程的。**

**6. 数组元素是通过“数组名\[下标\]”这样的形式来访问的。**

**7. 复合数据一般组织成对象,它们是由属性(attribute)和域(field)所组成的。**

**8. 参数采用按值传递方式:被调用的过程会收到参数的一份副本。**

**9. 布尔运算符"and”和"or”都是具有短路能力。**

**3. 算法分析即指对一个算法所需要的资源进行预测。**

**4. 对于一个算法,一般只考察其最坏情况的运行时间,理由有三:**

**1. 一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界。**

**2. 对于某些算法来说,最坏情况出现得还是相当频繁的。**

**3. 大致上看来,“平均情况”通常和最坏情况一样差。**

**5. 分治策略:将原问题划分成n个规模较小而结构与原问题相似的子问题;递归地解决这些小问题,然后再合并其结 果,就得到原问题的解。**

**6. 分治模式在每一层递归上都有三个步骤:**

**1. 分解(Divde):将原问题分解成一系列子问题;**

**2. 解决(Conquer):递归地解答各子问题。若子问题足够小,则直接求解; 3. 合并(Combine):将子问题的结果合并成原问题的解。**

# 下面具体介绍几个知识点： #

本章通过介绍插入排序和归并排序两种常见的排序算法来说明算法的过程及算法分析，在介绍归并排序算法过程中引入了分治（divide-and-conquer）算法策略。  
  
1、插入排序  
  
　　输入：n个数（a1,a2,a3,...,an）  
  
　　输出：输入序列的一个排列（a1',a2',a3',...an'）使得（a1'≤a2'≤a3'≤...≤an'）。  
  
　　插入排序的基本思想是：将第i个元素插入到前面i-1个已经有序的元素中。具体实现是从第2个元素开始（因为1个元素是有序的），将第2个元素插入到前面的1个元素中，构成两个有序的序列，然后从第3个元素开始，循环操作，直到把第n元素插入到前面n-1个元素中，最终使得n个元素是有序的。该算法设计的方法是增量方法。书中给出了插入排序的为代码，并采用循环不变式证明算法的正确性。我采用C语言实插入排序，完整程序如下：

void insert_sort(int *datas,int length)
 {
 int i,j;
 int key,tmp;
 //判断参数是否合法
 if(NULL == datas || 0==length)
 {
 printf("Check datas or length.\n");
 exit(1);
 }
 //数组下标是从0开始的，从第二个元素（对应下标1）开始向前插入
 for(j=1;j<length;j++)
 {
 key = datas[j]; //记录当前要插入的元素
 i = j-1; //前面已经有序的元素
 //寻找待插入元素的位置，从小到到排序，如果是从大到小改为datas[i]<key
 while(i>=0 && datas[i] > key)
 {
 /×tmp = datas[i+1];
 datas[i+1] = datas[i];
 datas[i] = tmp;×/ 这个过程不需要进行交换，因为要插入的值保存在key中，没有被覆盖掉，在此感谢”两生花“指出问题所在
 datas[i+1] = datas[i];
 i--; //向前移动
 }
 datas[i+1] = key; //最终确定待插入元素的位置
 }
 }

插入排序算法的分析  
  
　　算法分析是对一个算法所需的资源进行预测，资源是指希望测度的计算时间。插入排序过程的时间与输入相关的。插入排序的最好情况是输入数组开始时候就是满足要求的排好序的，时间代价为θ(n)，最坏情况下，输入数组是按逆序排序的，时间代价为θ(n^2)。  
  
2、归并排序  
  
　　归并排序采用了算法设计中的分治法，分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题，递归的解决这些子问题，然后再去合并其结果，得到原问题的解。分治模式在每一层递归上有三个步骤：  
  
分解（divide）：将原问题分解成一系列子问题。  
  
解决（conquer）：递归地解答各子问题，若子问题足够小，则直接求解。  
  
合并（combine）：将子问题的结果合并成原问题的解。  
  
归并排序（merge sort）算法按照分治模式，操作如下：  
  
分解：将n个元素分解成各含n/2个元素的子序列  
  
解决：用合并排序法对两个序列递归地排序  
  
合并：合并两个已排序的子序列以得到排序结果  
  
　　在对子序列排序时，长度为1时递归结束，单个元素被视为已排序好的。归并排序的关键步骤在于合并步骤中的合并两个已经有序的子序列，引入了一个辅助过程，merge(A,p,q,r)，将已经有序的子数组A\[p...q\]和A\[q+1...r\]合并成为有序的A\[p...r\]。书中给出了采用哨兵实现merge的伪代码，课后习题要求不使用哨兵实现merge过程。在这个两种方法中都需要引入额外的辅助空间，用来存放即将合并的有序子数组，总的空间大小为n。现在用C语言完整实现这两种方法，程序如下：

//采用哨兵实现merge
 #define MAXLIMIT 65535
 void merge(int *datas,int p,int q,int r)
 {
 int n1 = q-p+1; //第一个有序子数组元素个数
 int n2 = r-q; //第二个有序子数组元素个数
 int *left = (int*)malloc(sizeof(int)*(n1+1));
 int *right = (int*)malloc(sizeof(int)*(n2+1));
 int i,j,k;
 //将子数组复制到临时辅助空间
 for(i=0;i<n1;++i)
 left[i] = datas[p+i];
 for(j=0;j<n2;++j)
 right[j] = datas[q+j+1];
 //添加哨兵
 left[n1] = MAXLIMIT;
 right[n2] = MAXLIMIT;
 //从第一个元素开始合并
 i = 0;
 j = 0;
 //开始合并
 for(k=p;k<=r;k++)
 {
 if(left[i] < right[j])
 {
 datas[k] = left[i];
 i++;
 }
 else
 {
 datas[k] = right[j];
 j++;
 }
 }
 free(left);
 free(right);
 }

不采用哨兵实现，需要考虑两个子数组在合并的过程中哪一个先合并结束，剩下的那个子数组剩下部分复制到数组中，程序实现如下：

int merge(int *datas,int p,int q,int r)
 {
 int n1 = q-p+1;
 int n2 = r-q;
 int *left = (int*)malloc(sizeof(int)*(n1+1));
 int *right = (int*)malloc(sizeof(int)*(n2+1));
 int i,j,k;
 memcpy(left,datas+p,n1*sizeof(int));
 memcpy(right,datas+q+1,n2*sizeof(int));
 i = 0;
 j = 0;
 for(k=p;k<=r;++k)
 {
 if(i <n1 && j< n2) //归并两个子数组
 {
 if(left[i] < right[j])
 {
 datas[k] = left[i];
 i++;
 }
 else
 {
 datas[k] = right[j];
 j++;
 }
 }
 else
 break;
 }
 //将剩下的合并到数组中
 while(i != n1)
 datas[k++] = left[i++];
 while(j != n2)
 datas[k++] = right[j++];
 free(left);
 free(right);
 }

merge过程的运行时间是θ(n)，现将merge过程作为归并排序中的一个子程序使用，merge\_sort(A,p,r),对数组A\[p...r\]进行排序，实例分析如下图所示：

![Center][]

C语言实现如下：

void merge_sort(int *datas,int p,int r)
 {
 int q;
 if(p < r)
 {
 q = (p+r)/2; //分解，计算出子数组的中间位置 7 merge_sort(datas,p,q); //对第一个子数组排序;
 merge_sort(datas,q+1,r); //对第二个子数组排序
 merge(datas,p,q,r); //合并;
 }
 }

归并排序算法分析：  
  
　　算法中含有对其自身的递归调用，其运行时间可以用一个递归方程（或递归式）来表示。归并排序算法分析采用递归树进行，递归树的层数为lgn+1，每一层的时间代价是cn，整棵树的代价是cn(lgn+1)=cnlgn+cn，忽略低阶和常量c，得到结果为θ(nlg n)。

***练习***

**2.1-1：以图2-2为模型，说明INSERTION-SORT在数组A=<31,41,59,26,41,58>上的执行过程。**

**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** and A\[i\]<key

**6****do** A\[i+1\] ← A\[i\]

7 i←i-1

**7** A\[i+1\] ← key

**2.1-3：考虑下面的查找问题：**

**输入：**一列数A=<a1,a2,…,an >和一个值v

**输出：**下标i，使得v=A\[i\]，或者当v不在A中出现时为NIL。

**写出针对这个问题的现行查找的伪代码，它顺序地扫描整个序列以查找v。利用循环不变式证明算法的正确性。确保所给出的循环不变式满足三个必要的性质。**

LINEAR-SEARCH(A,v)

**1 for** i←1 **to** length\[A\]

**2 if** v=A\[i\]

**3 return** i

**4 return NIL**

现行查找算法正确性的证明。

**初始化：** i=1，子数组为A\[1..i\]，只有一个元素A\[1\],如果v=A\[1\]就返回1,否则返回NIL，算法显然是正确的。

**保持：**若算法对数组A\[1..i\]正确，则在数组增加一个元素A\[i+1\]时，只需要多作一次比较，因此显然对A\[1..i+1\]也正确。

**终止：**算法如果在非最坏情况下定能返回一个值此时查找成功，如果n次查找（遍历了所有的数）都没有成功，则返回NIL。算法在有限次查找后肯定能够给出一个返回值，要么说明查找成功并给出下标，要么说明无此值。因此算法正确。

该算法用C\#实现的代码：

public static int LinearSearch<T>(T\[\] Input, T v) where T:IComparable<T>

for (int i = 0; i < Input.Length;i++ )

if (Input\[i\].Equals(v))

return i;

return \-1;

**2.1-4：有两个各存放在数组A和B中的n位二进制整数，考虑它们的相加问题。两个整数的和以二进制形式存放在具有(n+1)个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。**

A存放了一个二进制n位整数的各位数值，B存放了另一个同样是二进制n位整数的各位上的数值，现在通过二进制的加法对这两个数进行计算，结果以二进制形式把各位上的数值存放在数组C（n+1位）中。

BINARY-ADD(A,B,C)

**1** flag← 0

**2 for j**←1 **to** n

**3 do** key←A\[j\]+B\[j\]+flag

4 C\[j\]← key **mod** 2

**5 if** key←1

**6**  flag←1

**7 if** flag=1

8 C\[n+1\]← 1

1.**RAM**(Random-Access Machine)模型分析通常能够很好地预测实际计算机上的性能，RAM计算模型中，指令一条接一条地执行，没有并发操作。RAM模型中包含了真实计算机中常见的指令：算术指令（加法、剑法、乘法、出发、取余、向下取整、向上取整指令）、数据移动指令（装入、存储、复制指令）和控制指令（条件和非条件转移、子程序调用和返回指令）。其中每天指令所需时间都为常量。

RAM模型中的数据类型有整数类型和浮点实数类型。

2.算法的运行时间是指在特定输入时，所执行的基本操作数（或步数）。

插入算法的分析比较简单，但是不是很有用，所以略过。（在解思考题2-1时有具体的实例分析，请参看）

3.一般考察算法的最坏情况运行时间。这样做的理由有三点：

A．一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界。

B．对于某些算法，最坏情况出现的是相当频繁的。

C．大致上来看，“平均情况“通常与最坏情况一样差。

4.如果一个算法的最坏情况运行时间要比另一个算法的低，我们常常就认为它的效率更高。

***练习***

**2.2-1：用Θ形式表示表示函数 /1000- -100n+3**

**Θ(n^3)**

**2.2-2:考虑对数组A中的n个数进行排序的问题：首先找出A中的最小元素，并将其与A\[1\]中的元素进行交换。接着，找出A中的次最小元素，并将其与A\[2\]中的元素进行交换。对A中头n-1个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序（selection sort）。对这个算法来说，循环不变式是什么?为什么它仅需要在头n-1个元素上运行，而不是在所有n个元素上运行？以 形式写出选择排序的最佳和最坏情况下的运行时间。**

假设函数MIN(A,i,n)从子数组A\[i..n\]中找出最小值并返回最小值的下标。

SELECTION-SORT(A)

**1 for** i**←**1 **to** n-1

**2** j**←**MIN(A,i,n)

**3**  exchange A\[i\]←→ A\[j\]

选择排序算法正确性的证明

**初始化：**i=1，从子数组A\[1..n\]里找到最小值A\[j\]，并与A\[i\]互换，此时子数组A\[1..i\]只有一个元素A\[1\]，显然是已排序的。

**保持：**若A\[1..i\]是已排序子数组。这里显然A\[1\] A\[2\] A\[3\] … A\[i\]，而A\[i+1..n\]里最小值也必大于A\[i\]，找出此最小值与A\[i+1\]互换并将A\[i+1\]插入A\[1..i\]得到子数组A\[1..i+1\]。A\[1..i+1\]显然也是已排序的。

**终止：**当i=n时终止，此时已得到已排序数组A\[1..n-1\]，而A\[n\]是经过n-1次比较后剩下的元素，因此A\[n\]大于A\[1..n-1\]中任意元素，故数组A\[1..n\]也即是原数组此时已是已排序的。所以，算法正确。

仅需要在头n-1个元素上运行是因为经过n-1次比较后剩下的是最大元素，其理应排在最后一个位置上，因此可以不必对此元素进行交换位置操作。

由于MIN()函数和SWAP()函数对于任意情况运行时间都相等，故这里最佳和最坏情况下运行时间是一样的。**Θ(n^2)**

选择算法的的C\#实现：

private static int Min<T>(T\[\] Input,int start,int end) where T:IComparable<T>

int flag=start;

for (int i = start; i < end; i++)

if (Input\[flag\].CompareTo(Input\[i\]) > 0)

flag = i;

return flag;

private static void Swap<T>(ref T a,ref T b) where T : IComparable<T>

T temp;

temp = a;

a = b;

b = temp;

public static T\[\] SelectionSort<T>(T\[\] Input) where T:IComparable<T>

for (int i = 0; i < Input.Length - 1; i++)

Swap(ref Input\[Min(Input, i, Input.Length)\],ref Input\[i\]);

return Input;

**2.2-3：再次考虑线性查找问题（见练习2.1-3）。在平均情况下，需要检查输入序列中的多少个元素？假定查找的元素是数组中任何一个元素的可能性都是相等的。在最坏情况下又怎么样呢？用Θ相似表示的话，线性查找的平均情况和最坏情况运行时间怎么样？对你的答案加以说明。**

平均：n/2次。因为任意一个元素大于、小于查找数的概率一样。

最坏：n次。最后一个元素才是要查找的元素。

用**Θ**表示都是：**Θ(n)**

**2.2-4：应如何修改一个算法，才能使之具有较好的最佳情况运行时间？**

要使算法具有较好的最佳情况运行时间就一定要对输入进行控制，使之偏向能够使得算法具有最佳运行情况的排列。

5.分治法（divide-and-conquer）:有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的问题。这些算法通常采用分治策略：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

容易确定运行时间，是分治算法的有点之一。

6.分治模式在每一层递归上都有三个步骤：

**分解（Divide）：**将原问题分解成一系列子问题；

**解决（Conquer）：**递归地解各子问题。若子问题足够小，则直接求解；

**合并（Combine）：**将子问题的结果合并成原问题的解。

7.合并排序（Merge Sort）算法完全依照了分治模式。

**分解：**将n个元素分成各含n/2个元素的子序列；

**解决：**用合并排序法对两个子序列递归地排序；

**合并：**合并两个已排序的子序列以得到排序结果。

在对子序列排序时，其长度为1时递归结束。单个元素被视为是已排好序的。

合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并，引入一个辅助过程MERGE(A,p,q,r)，其中A是个数组，p、q和r是下标，满足 。该过程假设子数组A\[p..q\]和A\[q+1..r\]都已排好序，并将他们合并成一个已排好序的子数组代替当前子数组A\[p..r\]。

MERGE过程的时间代价为**Θ(n)，**其中n=r-p+1是待合并的元素个数。

MERGE过程:

MERGE(A,p,q,r)

1 n1←q-p+n

2 n2←r-p

3 //create arrays L\[1..n1+1\] and R\[1..n2+1\]

4 **for** i←1 **to** n1

5  **do** L\[i\] ← A\[p+i-1\]

6 **for** j←1 **to n2**

7  **do** R\[j\] ← A\[q+j\]

8 L\[ \] ←无穷

9 R\[ \] ←无穷

10 i←1

11 j←1

**12 for k**←p **to** r

**13 do if** L\[i\]<= R\[j\]

**14  then** A\[k\] ← L\[i\]

15  **i**←i+1

**16** **else** A\[k\] ← R\[j\]

17  **j**←j+1

MERGE过程正确性的证明

**初始化：**第一轮循环，k=p，i=1，j=1，已排序数组L、R，比较两数组中最小元素L\[i\]、R\[j\]，取较小的置于A\[p\]，此时子数组A\[p..p\]不仅是已排序的（仅有一个元素），而且是所有待排序元素中最小的。若最小元素是L\[i\]，取i=i+1，即i指向L中未排入A的所有元素中最小的一个；同理，j之于R数组也是如此。

**保持：**若A\[p..k\]是已排序的，由计算方法知，L中i所指、R中j所指及其后任意元素均大于等于A\[p..k\]中最大元素A\[k\],当k=k+1，A\[k+1\]中存入的是L\[i\]、R\[j\]中较小的一个，但是仍有A\[k\] <= A\[k+1\]，而此时，子数组A\[p..k+1\]也必是有序的，i、j仍是分别指向L、R中未排入A的所有元素中最小的一个。

**终止：** k=r+1时终止跳出循环，此时，A\[p..r\]是已排序的，且显有A\[p\] A\[p+1\] .. A\[r\]。此即原待排序子数组，故算法正确。

MERGE-SORT(A,p,r)

1 **if** p<r

**2 then** q← \[(p+r)/2\]

3 MERGE-SORT(A,p,r)

4 MERGE-SORT(A,q+1,r)

5 MERGE-SORT(A,p,q,r)

算法与二叉树的后序遍历算法（先左子树，然后右子树，最后根）相似。

（第三行、第四行顺序可以互换）

合并排序算法的C\#实现代码：

public static void MergeSort<T>(T\[\] Input,int p,int r) where T:IComparable<T>

int q;

if (p < r)

q = (p + r) / 2;

MergeSort(Input, p, q);

MergeSort(Input, q + 1, r);

Merge(Input,p,q,r);

private static void Merge<T>(T\[\] Input,int p,int q,int r) where T:IComparable<T>

int n1 = q - p + 1;

int n2 = r - q;

T\[\] L = new T\[n1\];

T\[\] R = new T\[n2\];

for (int i = 0; i < n1; i++)

L\[i\] = Input\[p + i\];

for (int j = 0; j < n2; j++)

R\[j\] = Input\[q + 1 + j\];

for (int i = 0, j = 0, k = p; k <= r; k++)

if(i<n1&&j<n2)

if (L\[i\].CompareTo(R\[j\]) < 0||L\[i\].Equals(R\[j\]))

Input\[k\] = L\[i\];

\++i;

continue;

else

Input\[k\] = R\[j\];

\++j;

continue;

if (i >= n1 && j < n2)

Input\[k\] = R\[j\];

\++j;

continue;

if (i < n1 && j >= n2)

Input\[k\] = L\[i\];

\++i;

continue;

8.当一个算法中含有对其自身的递归调用时，其运行时间可以用一个递归方程（或递归式）来表示。

合并算法的递归式：

n<=c时,T(n)=Θ(1),否则T(n)=aT(n/b)+D(n)+C(n)

D(n)是分解该问题所用时间，C(n)是合并解的时间；对于合并排序算法，a和b都是2

T(n)在最坏的情况下合并排序n个数的运行时间分析:

当n>1时，将运行时间如下分解：

**分解：**这一步仅仅算出子数组的中间位置，需要常量时间，因而D(n)=Θ(1)

**解决：**递归地解为两个规模为n/2的子问题，时间为T(n/2)

**合并：**含有n个元素的子数组上，MERGE过程的运行时间为C(n) =Θ(n)

n=1时,T(n)=Θ(1),n>1时T(n)=2T(n/2)+ Θ(n)

将上式改写：

n=1时,T(n)=c,n>1时T(n)=2T(n/2)+ cn

在所构造的递归树中，顶层总代价为cn（n个点的集合）。往下每层总代价不变，第i层的任一节点代价为c(n/2^i)（共2^i个节点总代价仍然是cn）。最底层有n个节点（n\*1），每个点代价为c。此树共有lgn+1层，深度为lgn。

因此n层的总代价为：cn\*(lgn+1)=cnlgn+cn=Θ(nlgn)

***练习***

**2.3-1：2-4为模型，说明合并排序在输入数组A=<3,41,52,26,38,57,9,49>上的执行过程。**

以文字代替图示

1.(3)(41)→(3,41);(52)(26) →(26,52);(38)(57) →(38,57);(9)(49) →(9,49)

2.(3,41)(26,52) →(3,26,41,52);(38,57)(9,49) →(9,38,49,57)

3.(3,26,41,52)(9,38,49,57) →(3,9,26,38,41,49,52,57)

**2.3-2：MERGE过程，使之不适用哨兵元素，而是在一旦数组L或R中的所有元素都被复制回数组A后，就立即停止，再将另一个数组中余下的元素复制回数组A中**

MERGE(A,p,q,r)

1 n1←q-p+n

2 n2←r-p

3 //create arrays L\[1..n1\] and R\[1..n2\]

4 **for** i←1 **to** n1

5  **do** L\[i\] ←A\[p+i-1\]

6 **for** j←1 **to n2**

7  **do** R\[j\] ← A\[q+j\]

8 i←1

9 j←1

**10 for k**←p **to** r

**11 do if** i<n1 **and** j<n2

**12 if** L\[i\]<= R\[j\]

**13**  A\[k\] ← L\[i\]

**14**  i←i+1

**15 continue**

**16 else** A\[k\] ← R\[j\]

17 j←j+1

**18 continue**

**19 do if** i>=n1 **and** j<n2

20 A\[k\] ← R\[j\]

21 j←j+1

22 **continue**

**23 do if** i<n1 **and** j>n2

**24**  A\[k\] ← L\[i\]

**25**  i←i+1

**26 continue**

**2.3-3：利用数学归纳法证明：当n是2的整数次幂时，递归式**

**这个公式比较难贴上来，请大家看PDF。**

**2.3-4：插入排序可以如下改写成一个递归过程：为排序A\[1..n\]，先递归地排序A\[1..n-1\]，然后再将A\[n\]插入到已排序的数组A\[1..n-1\]中去。对于插入排序的这一递归版本，为它的运行时间写一个递归式。**

首先是INSERTION过程

INSERTION (A,p,r)

**1** **for** j←p **to** r

**2****do** key←A\[j\]

**3** i←j-1

**4****while** i>0 and A\[i\]>key

**5****do** A\[i+1\] ← A\[i\]

**6** i←i-1

**7** A\[i+1\] ← key

插入排序的递归调用算法：

RECURSION-INSERTION-SORT(A,p,r)

1 **if** p<r

2 r←r-1

3 RECURSION-INSERTION-SORT(A,p,r)

4 INSERTION(A,p,r)

该算法的C\#实现代码：

public static void RecursionInsertionSort<T>(T\[\] Input,int p,int r) where T:IComparable<T>

if (p < r)

\--r;

RecursionInsertionSort(Input, p, r);

Insertion(Input,p,r);

private static void Insertion<T>(T\[\] Input, int p, int r) where T : IComparable<T>

T key;

int i;

for (int j = 1; j < r; j++)

key = Input\[j\];

i = j - 1;

for (; i >= 0 && Input\[i\].CompareTo(key) > 0; i--)

Input\[i + 1\] = Input\[i\];

Input\[i + 1\] = key;

n<=C时，T(n)=Θ(1),否则T(n)=(n-1)/n\*T(n-1)+ Θ(n^2)

**2.3-5：回顾一下练习2.1-3中提出的查找问题，注意如果序列A是已排序的，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找（binary search）就是一个不断重复这一查找过程的算法，它每次都将序列余下的部分分成两半，并只对其中的一半做进一步的查找。写出二分查找算法的伪代码，可以是迭代的，也可以是递归的。说明二分查找的最坏情况运行时间为什么是Θ(lgn)。**

使用递归，先确定一个过程BINARY(A,p,r,v)

BINARY(A,p,r,v)

1 **for** j← p **to** r

**2 if** A\[j\]=v

**3 return** j

**4 return NIL**

**然后是二分查找的递归过程**

BINARY-SEARCH(A,p,r,v)

**1 if** p=0 and r=0 and A\[0\]=v

**2**  return 0

3 **if** p<r

**4** q←\[(p+r)/2\]

**5 if** A\[q\]> v

**6**  BINARY-SEARCH(A,p,q,v)

**7 return** BINARY(A,p,q,v)

**8 else** BINARY-SEARCH(A,q+1,r,v)

**9 return** BINARY(A,q+1,r,v)

**10 return NIL**

**该算法的C\#实现代码：**

public static int BinarySearch<T>(T\[\] Input,int p,int r,T v) where T:IComparable<T>

int q;

if (p == 0 && r == 0 && Input\[0\].Equals(v))

return 0;

if (p < r)

q = (p + r) / 2;

if (Input\[q\].CompareTo(v) > 0 )

BinarySearch(Input, p, q, v);

return Binary(Input, p, q, v);

else

BinarySearch(Input, q + 1, r, v);

return Binary(Input, q+1, r, v);

return \-1;

private static int Binary<T>(T\[\] Input, int p, int r, T v) where T:IComparable<T>

for (int j = p; j <= r; j++)

if (Input\[j\].Equals(v))

return j;

return \-1;

由公式N=a^(log a N)得：n\*1/(2^(lgn))=1

因经过n次的与中点比较后肯定能找到最后一个点（最坏情况了），如果是返回下标，否则返回NIL，故最坏情况下时间复杂度为

**2.3-6：观察一下2.1节中给出的INSERTION-SORT过程，在第5~7行的while循环中，采用了一种线性查找策略，在已排序的子数组A\[1..j-1\]中（反向）扫描。是否可以改为二分查找策略（见练习2.3-5），来将插入排序的总体最坏情况运行时间改善至**Θ(nlgn)**？**

首先引入一个二分查找策略（与2.3-5的Binary Search略有不同）

BINARY(A,p,r,v)

5 **for** j←p **to** r

**6** **if** A\[j\]> v

**7 return** j

**8 return NIL**

**然后是二分查找的递归过程**

BINARY-SEARCH(A,p,r,v)

**10** **if** p=0 and r=0 and A\[0\] v

**11 return** 0

12 **if** p<r

**13**

**14 if** A\[q\] v

**15**  BINARY-SEARCH(A,p,q,v)

**16 return** BINARY(A,p,q,v)

**17 else** BINARY-SEARCH(A,q+1,r,v)

**18 return** BINARY(A,q+1,r,v)

**10 return NIL**

利用了二分查找策略的插入排序：

BINARYINSERTION-SORT(A)

1 **for** j 2 **to** length\[A\]

2  **do** key A\[j\]

3 i j-1

4 k BINARY-SEARCH(A,0,i,key)

5 if k!= NIL

**6 for** s i downto k

**7**  A\[s+1\] A\[s\]

**8**  A\[k\] key

此算法的在最坏情况下的运行时间是

该算法的C\#实现代码：

private static int BinarySearchForInsertionSort<T>(T\[\] Input, int p, int r, T v) where T : IComparable<T>

int q;

if (p == 0 && r == 0 && Input\[0\].CompareTo(v)>0)

return 0;

if (p < r)

q = (p + r) / 2;

if (Input\[q\].CompareTo(v) > 0)

BinarySearchForInsertionSort(Input, p, q, v);

return BinaryForInsertionSort(Input, p, q, v);

else

BinarySearchForInsertionSort(Input, q+1, r, v);

return BinaryForInsertionSort(Input, q+1, r, v);

return \-1;

private static int BinaryForInsertionSort<T>(T\[\] Input, int p, int r, T v) where T : IComparable<T>

for (int j = p; j <= r; j++)

if (Input\[j\].CompareTo(v) > 0)

return j;

return \-1;

public static void BinaryInsertionSort<T>(T\[\] Input) where T : IComparable<T>

T key;

int i, k;

for (int j = 1; j < Input.Length; j++)

key = Input\[j\];

i = j - 1;

k = BinarySearchForInsertionSort(Input, 0, i, key);

if (k != -1)

for (int s = i; s>=k ; s--)

Input\[s + 1\] = Input\[s\];

Input\[k\] = key;

**\*2.3-7：请给出一个运行时间为**Θ(nlgn)**的算法，使之能在给定一个由n个整数构成的集合 和另一个整数 时，判断出 中是否存在有两个其和等于 的元素。**

利用2.3-5中的BINARY-SEARCH(A,v)和2.3-6中的BINARYINSERTION-SORT(S)算法

ISEXISTSUM(S,x)

1 BINARYINSERTION-SORT(S)

**2 for** j←)1 to n

3 k BINARY-SEARCH(S,x-S\[j\])

4 **if** k!=**NIL**

5  **return TRUE**

6  **else return FALSE**

该算法的运行时间为: Θ(nlgn)

***思考题***

**2-1：在合并排序中对小数组采用插入排序**

**尽管合并排序的最坏情况运行时间为**Θ(nlgn)**，插入排序的最坏情况运行时间为**Θ(n^2)**，但插入排序中的常数因子使得它在n较小时，运行得要更快一些。因此，在合并排序算法中，当子问题足够小时，采用插入排序就比较合适了。考虑对合并排序做这样的修改，即采用插入排序策略，对n/k个长度为k的子列表进行排序，然后，再用标准的合并机制将它们合并起来，此处k是一个特定的值。**

**a) 证明最坏情况下，n/k个子列表（每一个子列表的长度为k）可以用插入排序在**Θ(nk)**时间内完成排序。**

**b) 证明这些子列表可以在**Θ(nlg(n/k))**最坏情况时间内完成合并。**

**c) 如果已知修改后的合并排序算法的最坏情况运行时间为**Θ(nk+nlg(n/k))**，要使修改后的算法具有与标准合并排序算法一样的渐进运行时间，k的最大渐进值（即 形式）是什么（以n的函数形式表示）？**

**d) 在实践中，k的值应该如何选取？**

a.Θ(k^2\*n/k)= Θ(nk)

b.每一层代价都是Θ(n)，共lg(n/k)+1层，因此相乘得Θ(nlg(n/k))

c.k=lgn

d.在满足插入排序比合并排序更快的情况下，k取最大值。

**2-2：冒泡排序算法的正确性**

**冒泡排序(bubblesort)算法是一种流行的排序算法，它重复地交换相邻两个反序元素。**

**BUBBLESORT(A)**

**1 for** i←1 **to** length\[A\]

**2 do for** j←length\[A\] **downto** i+1

**3 do if** A\[j\]< A\[j-1\]

**4 then** exchange A\[j\]←→ A\[j-1\]

**a) 设A’表示BULLESORT(A)的输出，为了证明BUBBLESORT是正确的，需要证明它能够终止，并且有：A’\[1\]<=A’\[2\]<=..<=A’\[n\]**

**其中n=length\[A\]。为了证明BUBBLESORT的确能实现排序的效果，还需要证明什么？**

**下面两个部分将证明不等式（2.3）。**

**b) 对第2~4行中的for循环，给出一个准确的循环不变式，并证明该循环不变式是成立的。在证明中采用本章中给出的循环不变式证明结构。**

**c) 利用在b）部分证明的循环不变式的终止条件，为第1~4行中的for循环给出一个循环不变式，它可以用来证明不等式（2.3）。你的证明因采用本章中给出的循环不变式的证明结构。**

**d) 冒泡排序算法的最坏情况运行时间是什么？比较它与插入排序的运行时间。**

a. A’中的元素全部来自于A中变换后的元素。

**初始化：**j=n,子数组为A\[j..n\]即A\[n..n\]，此中仅有一个元素因此是已排序的。

**保持：**如果A\[j..n\]是已排序的，按计算过程知A\[j\] A\[j+1\] … A\[n\]，当插入元素A\[j-1\]时，如果A\[j\] A\[j-1\]则互换A\[j\]、A\[j-1\]，否则A\[j-1\]直接插入A\[j..n\]的最前，因此A\[j-1..n\]也是已排序的。

**终止：**j=i时循环结束，此时A\[i..n\]是已排序的。与外层循环条件一直，所以算法正确。

**初始化：**i=1时，子数组A\[1..i-1\]是空的，因此在第一轮迭代前成立。

**保持：**假设子数组A\[1..i-1\]已排序，则之中元素是A\[1..n\]中最小的i-1个元素，按b证明的循环不变式，知插入A\[i\]元素后的子数组A\[1..i\]是A\[1..n\]中最小的i个元素，并且A\[1..i\]亦是已排序的。

**终止：**当i=n+1时循环终止，此时已处理的子数组是A\[1..n\]，A\[1..n\]是已排序的，这个数组就是要排序的数组。因此算法正确。

d.Σ（n-i）+Σ（n-i-1）=Θ（n^2）,与插入排序相同

**2-3：霍纳规则的正确性**

**以下的代码片段实现了用于计算多项式**

**代码片段见PDF**

**的霍纳规则（Horner’s Rule）。**

**给定系数a0,a1,…an以及x的值，有**

1 y←0

2 i←n