Chapter 2
插入排序
线性查找
选择算法
归并排序算法
二分查找算法
冒泡排序
插入排序
INSERTION-SORT(A)
for j=2 to A.length
key = A[j]
//insert A[j] into the sortes 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
function insertion_sort(arr) {
var key = 0;
var i = 0;
for(var j = 1; j < arr.length; j++) {
key = arr[j];
i = j - 1;
while (i >= 0 && arr[i] > key) {
arr[i+1] = arr[i];
i = i - 1;
}
arr[i+1] = key;
}
return arr;
}
循环不变式
初始化：循环第一次迭代之前，它为真
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的
算法分析
| INSERTION-SORT(A) | 代价 | 次数 |
|---|---|---|
| for j=2 to A.length | c1 | n |
| key = A[j] | c2 | n-1 |
| //insert A[j] into the sortes sequence A[1...j-1] | 0 | n-1 |
| i = j-1 | c4 | n-1 |
| while i>0 and A[i]>key | c5 | ∑tj (2<=j<=n) |
| A[i+1] = A[i] | c6 | ∑(tj - 1) (2<=j<=n) |
| i = i-1 | c7 | ∑(tj - 1) (2<=j<=n) |
| A[i+1] = key | c8 | n-1 |
tj 表示对那个值j第5行执行while循环测试的次数
所以，T(n) = c1n + c2(n-1) + c4(n-1) + c5∑tj (2<=j<=n) + c6∑(tj - 1) (2<=j<=n) + c7∑(tj - 1) (2<=j<=n) + c8(n-1)
最佳情况：对j=2, 3, ..., n，有tj = 1，所以 T(n) = (c1 + c2 + c4 + c5 +c8)n - (c2 + c4 + c5 + c8) = Θ(n)
最坏情况：对j=2, 3, ..., n，有tj = j，所以 ∑tj (2<=j<=n) = ∑j (2<=j<=n) = n(n+1)/2 - 1, ∑(tj - 1) (2<=j<=n) = n(n-1)/2, T(n) = (c5 + c6 + c7)n^2/2 + (c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8)n - (c2 + c4 + c5 + c8) = Θ(n^2)
分治模式
分治模式在每层递归时都有三个步骤：
分解原问题为若干个子问题，这些字问题是原问题的规模较小的实例。
解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
合并这些子问题的解成原问题的解。
归并排序算法
归并排序算法完全遵循分治模式。直观上其操作如下：
分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
解决：使用归并排序递归地排序两个子序列。
合并：合并两个已排序的子序列以产生已排序的答案。
通过调用一个辅助过程MERGE(A, p, q, r)来完成两个已排序序列的合并，其中A是一个数组，p、q和r是数组下标，满足 p<=q<r。该过程假设子数组A[p..q]和A[q+1..r]都已排好序。它合并两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p..r]。
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
Let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q+j]
//插入哨兵牌
L[n1 + 1] = ∞
R[n2 + 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, 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)
分析分治算法
分治算法运行时间的递归式来自基本模式的单个步骤。假设T(n)是规模为n的一个问题的运行时间。若问题规模足够小，如对某个常量c，n<=c，则直接求解需要常量时间，将其记作Θ(1)。假设把原问题分解成a个子问题，每个子问题的规模是原问题的1/b。为了求解一个规模为n/b的子问题，需要T(n/b)的时间，所以，需要aT(n/b)的时间来求解a个子问题，如果分解问题成子问题需要时间D(n)，合并子问题的解成原问题的解需要C(n)，那么得到递归式：
若n<=c，T(n) = Θ(1)；其他，T(n) = aT(n/b) + D(n) + C(n)
所以，归并排序的最坏情况运行时间T(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
对递归式T(n) = 2T(n/2) + cn构造递归树，如下：
所以，T(n) = Θ(nlgn)
练习
2.1-2 重写INSERTION-SORT，使之按非升序排列
INSERTION-SORT2(A)
for j=2 to A.length
key = A[j]
i = j-1
while i > 0 and A[i] < key
A[i+1] = A[i]
i = i-1
A[i+1] = key
function insertion_sort2(arr) {
var key = 0;
var i = 0;
for(var j = 1; j < arr.length; j++) {
key = arr[j];
i = j - 1;
while (i >= 0 && arr[i] < key) {
arr[i+1] = arr[i];
i = i - 1;
}
arr[i+1] = key;
}
return arr;
}
2.1-3 考虑一下查找问题：
输入：n个数的一个序列 A=<a1, a2, ..., an> 和一个值v
输出：下标i是的 v=A[i] 或者当v不在A中出现时，v为特殊值NIL
写出线性查找的伪代码，它扫描整个序列来查找v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。
LINEAR-SEARCH(A, v)
for i=1 to A.length
if A[i] equals v
return i
return NIL
function linear_search(arr, v) {
for(var i = 0; i < arr.length; i++) {
if (arr[i] === v) {
return i+1;
}
}
return null;
}
2.1-4 考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个(n+1)元数组C中。请给出该问题的形式化描述，并写出伪代码。
输入：两个n元数组A和B
输出：一个(n+1)元数组C
BINARY-ADD(A, B)
for i=A.length to 1
tmp = A[i] + B[i] + tmp;
if tmp > 1
C[i+1] = tmp - 2
tmp = 1
else C[i+1] = tmp
tmp = 0
C[1] = tmp
function binary_add(arr1, arr2) {
var arr3 = [];
var tmp = 0;
for(var i = arr1.length-1; i >= 0; i--) {
tmp = arr1[i] + arr2[i] + tmp;
if (tmp > 1) {
arr3[i+1] = tmp - 2;
tmp = 1;
}
else {
arr3[i+1] = tmp;
tmp = 0;
}
}
arr3[0] = tmp;
return arr3;
}
2.2-1 用Θ记号表示函数n3/1000-100n2-100n+3
Θ(n^3)
2.2-2 考虑排序存储在数组A中的n个数：首先找出A中的最小元素并将其与A[1]中的元素进行交换。接着，找出A中的次最小元素并将其与A[2]中的元素进行交换。对A中前n-1个元素按该方式继续。这算法称为选择算法，写出其伪代码。该算法维持的循环不变式是什么？为什么它只需要对前n-1个元素，而不是对所有n个元素运行？用Θ记号给出选择排序的最好情况与最坏情况运行时间
SELECTION(A)
for j=1 to A.length-1
min = A[j]
pointer = j
for i=j to A.length
if A[i] < min
min = A[i]
pointer = i
A[pointer] = A[j]
A[j] = min
function selection(arr) {
var min = 0;
var pointer = 0;
for(var j = 0; j < arr.length - 1; j++) {
min = arr[j];
pointer = j;
for(var i = j; i <arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
pointer = i;
}
}
arr[pointer] = arr[j];
arr[j] = min;
}
return arr;
}
因为第n个元素在进过前n-1个循环后一定是最大的，所以不需要对它在进行操作。
Θbest = Θ(n^2)
Θworest = Θ(n^3) Θ(n^2)
2.2-3 再次考虑线性查找问题（参见练习2.1-3）。假定要查找的元素等可能地为数组中的任意元素，平均需要检查的输入序列的多少元素？最坏情况又如何？用Θ记号给出线性查找的平均情况和最坏情况运行时间。证明你的答案
平均情况 T(n) = 1/(n+1) + 2/(n+1) + 3/(n+1) + ... + n/(n+1) + n/(n+1) = (n^2 + 3n)/2(n+1) = Θ(n)
最坏情况 T(n) = Θ(n)
2.3-2 重写过程MERGE，使之不使用哨兵，而是一旦数组L或R的所有元素均被复制回A就立刻停止，然后把两一个数组的剩余部分复制回A
MERGE2(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1..n1] and R[1.. n2] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q + j]
i = 1
j = 1
for k = p to r
if (L[i] <= R[j] or j > n2)
A[k] = L[i]
i = i + 1
else if (L[i] > R[j] or i > n1)
A[k] = R[j]
j = j + 1
var arr = [10,7,3,9,2,9,4,5,6,11];
function merge2(p, q, r) {
var n1 = q - p + 1;
var n2 = r - q;
var arrL = [];
var arrR = [];
var i = 0, j = 0;
for (i = 0; i < n1; i++) {
arrL[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
arrR[j] = arr[q + j + 1];
}
i = 0;
j = 0;
var k = 0;
for (k = p; k < r + 1; k++) {
if (arrL[i] <= arrR[j] || j >= n2) {
arr[k] = arrL[i];
i = i + 1;
} else if (arrL[i] > arrR[j] || i >= n1) {
arr[k] = arrR[j];
j = j + 1;
}
}
}
function merge_sort(p, r) {
var mid = 0;
if (p < r) {
mid = Math.floor((p + r)/2);
merge_sort(p, mid);
merge_sort(mid+1, r);
merge2(p, mid, r);
}
}
merge_sort(0, arr.length-1);
console.log(arr);
2.3-4 我们可以把插入排序表示为如下的一个递归过程。为了排序A[1..n]，我们递归地排序A[1..n-1]，然后把A[n]插入到已排序的数组A[1..n-1]。为插入排序的这个递归版本的最坏情况运行时间写一个递归式
如果n = 1，T(1) = 1；
如果n > 1，将A[n]插入A[1..n-1]需要比进行n-1次比较，所以 T(n) = T(n-1) + c(n-1)
2.3-5 回顾线性查找问题，注意到，如果序列A已排好序，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程，每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明：二分查找的最坏运行时间为Θ(lgn)
BINARY-SEARCH(A, key)
start = 1
end = A.length
while (start <= end)
i = └(start + end) / 2┘
if (A[i] == key)
return i
else if (A[i] > key)
end = i - 1
else if (A[i] < key)
start = i + 1
return "NF"
function binary_search(array, key) {
var start = 0, end = array.length-1;
var i = 0;
while (start <= end) {
i = Math.floor((start + end)/2);
if (array[i] === key) {
return i;
} else if (array[i] > key) {
end = i - 1;
} else if (array[i] < key) {
start = i + 1;
}
}
return "NF";
}
如果n = 1，T(1) = 1；
如果n > 1, 最差的情况就是比较到最后一位，得出结论，所以T(n)=lgn
2.3-6 注意插入排序的第5~7行的while循环采用一种线性查找来（反向）扫描已排好序的子数组A[1..j-1]。我们可以使用二分查找来把插入排序的最坏情况运行总时间改进到Θ(nlgn)吗？
INSERTION-SORT2(A)
for i=2 to A.length
newA = A.slice(0,1)
key = A[i]
answer = BINARY-SEARCH(newA, key)
for j=i down to answer
A[j] = A[j-1]
A[answer] = key
function binary_search(array, key) {
var start = 0, end = array.length-1;
var i = 0;
while (start <= end) {
i = Math.floor((start + end)/2);
if (array[i] === key) {
return i;
} else if (array[i] > key) {
end = i - 1;
} else if (array[i] < key) {
start = i + 1;
}
}
return (start < end)? end: start;
}
function insertion_sort2(array) {
for (var i = 1; i < array.length; i++) {
var new_array = array.slice(0, i);
var key = array[i];
var answer = binary_search(new_array, key);
for(var j = i; j > answer; j--) {
array[j] = array[j-1];
}
array[answer] = key;
}
return array;
}
2.3-7 描述一个运行时间为Θ(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。
function determineSumX(array, x) {
var filtered = array.filter(function(e) {
return e<x;
});
var sorted = insertion_sort2(filtered);
var start = 0, end = sorted.length-1;
while(start < end) {
if (sorted[start] + sorted[end] === x) {
return true;
} else if (sorted[start] + sorted[end] < x) {
start = start + 1;
} else if (sorted[start] + sorted[end] > x) {
end = end - 1;
}
}
return false;
}
function binary_search(array, key) {
var start = 0, end = array.length-1;
var i = 0;
while (start <= end) {
i = Math.floor((start + end)/2);
if (array[i] === key) {
return i;
} else if (array[i] > key) {
end = i - 1;
} else if (array[i] < key) {
start = i + 1;
}
}
return (start < end)? end: start;
}
function insertion_sort2(array) {
for (var i = 1; i < array.length; i++) {
var new_array = array.slice(0, i);
var key = array[i];
var answer = binary_search(new_array, key);
for(var j = i; j > answer; j--) {
array[j] = array[j-1];
}
array[answer] = key;
}
return array;
}
2.1 （在归并排序中对小数组采用插入排序）虽然归并排序的最坏情况运行时间为Θ(nlgn)，而插入排序的最坏运行时间为Θ(n^2)，但是插入牌组中的常量因子可能使得它在n较小时，在许多机器上实际运行得更快。因此，在归并排序中，当子问题变得足够小时，采用插入排序来使递归的叶变粗是有意义的。考虑对归并排序的一种修改，其中使用插入排序来排序长度为k的n/k个子表，然后使用标准的合并机制来合并这些子表，这里k是一个待定的值。
a. 证明：插入排序最坏的情况可以在Θ(nk)时间内排序每个长度为k的n/k个子表。
b. 表明在最坏的情况下如何在Θ(nlg(n/k))时间内合并这些子表。
c. 假定修改后的算法的最坏情况运行时间为Θ(nk+nlg(n/k))，要使修改后的算法与标准的归并排序具有相同的运行时间，作为n的一个函数，借助Θ记号，k的最大值是什么？
d. 在实践中，我们应该如何选择k？
a. 因为插入排序的最坏运行时间为Θ(n2)，所以对于长度为k的1个子表，最坏运行时间为Θ(k2)；
又因为一共有n/k个子表，所以，最坏运行时间为(n/k)*Θ(k^2) = Θ(nk)。
b. 由结果递归树可得，最小的叶子节点为cn/k，共有k个叶子节点，所以树的高度为lg(n/k)，又每层将贡献总代价cn，所以，总代价为cn(lg(n/k)+1)，也就是Θ(nlog(n/k))。
c. Θ(nk + nlg(n/k)) = Θ(nlgn)，=>Θ(k+lg(n/k)) = Θ(lgn)，所以k<lgn，k的最大值应该是lgn。
d. 这是个实验问题，应该在k的合法范围内测试可能的k，用T-INSERTION-SORT(k)表示k个元素的插入排序时间，T-MERGE-SORT(k)表示k个元素的合并排序时间。该问题等价于测试求解T-INSERTION-SORT(k)/T-MERGE-SORT(k)比值最小的k值。
2.2 （冒泡排序算法的正确性）冒泡排序算法是一种流行但低效的排序算法，它的作用是反复交换相邻的未按次序排列的元素。
BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A[j] < A[j-1]
4 exchange A[j] with A[j-1]
a. 假设A′表示BUBBLESORT(A)的输出。为了证明BUBBLESORT正确，我们必须证明它将终止并且有：
A'[1] ≤ A'[2] ≤ ... ≤ A'[n] (2.3)
其中 n=A.length。为了证明BUBBLESORT确实完成了排序我们还需要证明什么？
下面两个部分将证明不等式（2.3）。
b. 为第2~4行的for循环精确地说明一个循环不变式，并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结构。
c. 利用在(b)部分证明的循环不变式的终止条件，为第1~4行的for循环说明一个循环不变式，它可以用来证明不等式(2.3)。你的证明应采用本章中给出的循环不变式的证明结构。
d. 冒泡排序算法的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？
a. 当n=1时，能够正确排序。
b. 对第2~4行的for循环，循环不变式是A[j]是子数组A[j…n]中的最小值，且子数组中的元素并未改变。约定：n=A.length。
初始化：开始时，j=n，子数组中只包含A[n]，故循环不变式成立
保持：假设对于任意的一个j，使得A[j]是子数组A[j…n]中的最小值，在下一轮循环中，若A[j] < A[j-1]，则A[j]和A[j-1]交换。使得A[j-1]是子数组A[j-1…n]中的最小值，循环不变式依然成立
终止：循环结束时j=i，A[j]是子数组A[j…n]中的最小值，且子数组中的元素并未改变。
c. 对于1~4行的for循环，循环不变式是每次循环前，A[1…i-1]中包含了整个数组中前i-1小的排好序的元素，而A[i…n]中包含剩下的元素。
初始化：第一次循环前i=1，子数组为空，循环不变式成立
保持：假设对于任意一个i，使得A[1…i-1]中包含了整个数组中前i-1小的排好序的元素，而A[i…n]中包含剩下的元素，则内层循环保证了A[i]是子数组A[i…n]中的最小元素，则A[1…i]中包含了整个数组中前i小的排好序的元素，而A[i+1…n]中包含剩下的元素。循环不变式成立
终止：循环结束时i=n+1，则A[1…n]中包含了整个数组中前n小的排好序的元素，即数组有序。
d. 冒泡排序最坏和最好运行时间均为Θ(n^2)
插入排序的最坏运行时间为Θ(n^2)，但是最好运行时间为Θ(n)
排序前A所有元素已经有序时，插入排序达到最好运行时间。
2.3 （霍纳(Horner)规则的正确性）给定系数a0, a1, …, an和x的值，代码片段
1 y = 0
2 for i = n downto 0
3 y = ai + x·y
实现了用于求值多项式
![]()
的霍纳规则。
a. 借助Θ记号，实现霍纳规则的以上代码片段的运行时间是多少？
b. 编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳规则相比，其性能如何？
c. 考虑以下循环不变式：
在第2～3行for循环每次迭代的开始有
![]()
把没有项的和式解释为等于0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有
![]()
d. 最后证明上面给出的代码片段将正确地求由系数a0, a1, …, an刻画的多项式的值。
a. Θ(n)
b. 伪代码如下：
y = 0
tmp = 1
for k = 0 to n
y = y + ak * tmp
tmp = tmp * x
该算法的时间复杂度为：Θ(n^2)
c. 证明如下：
初始化：i=n时，y=0
保持：对于任意 0 ≤ i ≤ n，迭代的开始有y=Σ a[k+i+1] * x^k =a[k+i+1] + a[k+i+2] * x + ... + an * x^(n-(i+1))，循环后有：y[i] = a[i] + y[i+1] * x = a[i] + (a[i+1] * x + a[i+2] * x + ... + a[n] * x^(n-(i+1))) * x = a[i] + a[i+1] * x + a[i+2] * x^2 + ... + a[n] * x^(n-i)
终止：i=0时，循环终止，i=0开始前有y=Σ a[k+1] * x^k = a[1] + a[2] * x + a[n] * x^(n-1)，执行循环，y=a0 + x * [a[1] + a[2] * x + a[n] * x^(n-1)] = a0 + a[1]x + a[2]x^2 + ... + a[n]*x^n。
d. <我并没有看懂>
2.4 （逆序对）假设A[1..n]是一个有n个不同数的数组。若i < j且A[i] > A[j]，则对偶(i, j)称为A的一个逆序对(inversion)。
a. 列出数组 <2, 3, 8, 6, 1> 的5个逆序对。
b. 由集合 {1, 2，…，n} 中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？
c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。
d. 给出一个确定在n个元素的任何排列中逆序对数量的算法，最坏情况需要 Θ(nlgn) 时间。（提示：修改归并排序。）
a. (2, 1), (3, 1), (8, 6), (8, 1), (6, 1)
b. <n, n-1, n-2, ..., 1>拥有最多的逆序对，共有 n*(n-1)/2
c. 逆序对越多，插入排序的复杂度越大
排序n个数，如果不存在逆序对，则插入排序的复杂度为Θ(n)，每多一个，复杂度加1
d. 如下：
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
Let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q+j]
//插入哨兵牌
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
count = 0
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
count = count + 1
