練習
2.1-1 以圖2-2為模型垮耳，說明INSERTION-SORT在數(shù)組A=[31,41,59,26,41,58]上的執(zhí)行過程栅屏。
[31,41,59,26,41,58] key = 41
[31,41,59,26,41,58] key = 59
[31,41,59,26,41,58] key = 26
[31,41,59,59,41,58] key = 26
[31,41,41,59,41,58] key = 26
[31,31,41,59,41,58] key = 26
[26,31,41,59,41,58] key = 26
[26,31,41,59,41,58] key = 41
[26,31,41,59,59,58] key = 41
[26,31,41,41,59,58] key = 41
[26,31,41,41,59,58] key = 58
[26,31,41,41,59,59] key = 58
[26,31,41,41,58,59] key = NIL
2.1-2 重寫過程INSERTION-SORT，使之按照非升序排序。
void INSERTION_SORT(int A[], int len)
{
for (int i = 1; i < len; ++i) {
int j = i;
int val = A[j];
while (j > 0 && val > A[j - 1]) {
A[j] = A[j - 1];
j = j - 1;
}
A[j] = val;
}
}
2.1-3 考慮以下查找問題：
輸入：n個數(shù)的一個序列A={a[i]}和一個值v。
輸出：下標i使得v=A[i]或者當v不在A中出現(xiàn)時佃乘，v為特殊值NIL。
寫出線性查找的偽代碼麦锯，它掃描整個序列來查找v恕稠。使用一個循環(huán)不變式來證明你的算法是正確的。確保你的循環(huán)不變式滿足三條必要的性質(zhì)扶欣。
int search(int A[], int len, int v)
{
for (int i = 0; i < len; ++i) {
if (v = A[i]) return i;
}
return -1;
}
初始化：i的值為0鹅巍，且i < len成立。
保持：每次迭代之后i自增1料祠，當i < len時總是滿足條件骆捧，且0~i-1之間的元素是被檢查過的。
終止：要么在每次循環(huán)中滿足條件v = A[i]后終止髓绽；要么當i不小于len后終止敛苇，這時0~n - 1的元素是被檢查過的，故算法正確顺呕。
2.1-4 考慮把兩個n位二進制整數(shù)加起來的問題枫攀，這兩個整數(shù)分別存儲在兩個n元數(shù)組A和B中。這兩個整數(shù)的和應該按照二進制形式存儲在一個(n + 1)元數(shù)組C中株茶。請給出該問題的形式化描述来涨，并寫出偽代碼。
int* binary_sum(int A[], int B[], int n)
{
int* C = new int[n + 1];
int is_overflow = 0;
for (int i = n - 1, k = n; i >= 0; --i, --k) {
C[k] = A[i] + B[i] + is_overflow;
if (C[k] > 1) is_overflow = 1;
else is_overflow = 0;
C[k] %= 2;
}
C[k] = is_overflow;
return C;
}
練習
2.2-1 用Θ記號表示函數(shù)n^3 / 1000 - 100n^2 - 100n + 3启盛。
取最大項并且舍去常數(shù)系數(shù)得到：Θ(n^3)
2.2-2 考慮排序存儲在A數(shù)組A中的n個數(shù)：首先找出A中的最小元素并將其與A[1]中的元素進行交換蹦掐。接著技羔，找出A中次小的元素并將其與A[2]中的元素進行交換。對A中前n - 1個元素按該方式繼續(xù)卧抗。該算法稱為選擇算法藤滥，寫出偽代碼。該算法維持的循環(huán)不變式是什么社裆？為什么它只需要對前n-1個元素拙绊，而不是對所有n個元素運行？用Θ記號給出選擇排序的最好情況和最快情況運行時間浦马。
void selection_sort(int A[], int len)
{
for (int i = 0; i < len - 1; ++i) {
int min_index = i;
for (int j = i; j < len; ++j) {
if (A[j] < A[min_index]) min_index = j;
}
std::swap(A[i], A[min_index]);
}
}
因為前n-1個元素就位的時候时呀，第n個元素也一定會就位，所以只用處理n-1個元素晶默。
最好情況：Θ(n^2)。因為不管怎樣航攒，都要進行元素檢查磺陡，即使數(shù)組是有序的。
最壞情況：Θ(n^2)漠畜。
2.2-3 再次考慮線性查找問題币他，假定要查找的元素等可能的為數(shù)組中的任意元素，平均需要檢查輸入序列的多少元素憔狞？最壞情況又如何呢蝴悉？用Θ記號給出線性查找的平均情況和最壞運行情況。證明你的答案瘾敢。
最好的情況是第一個元素就找到拍冠，只需要常數(shù)的時間，而最壞的情況則需要遍歷整個數(shù)組才能找到簇抵，需要n的時間庆杜。于是平均需要檢查(n + 1) / 2個元素。
平均情況：Θ(n)碟摆。這里舍去了常數(shù)系數(shù)晃财。
最壞情況：Θ(n)。
2.2-4 我們可以如何修改幾乎任意算法來使之具有良好的運行情況運行時間典蜕？
根據(jù)輸入數(shù)據(jù)的情況去專門設計算法断盛，也就是倒推。
練習
2.3-1 使用圖2-4作為模型愉舔，說明歸并排序在數(shù)組A = [3,41,52,26,38,57,9,49]上的操作钢猛。
[3,41,52,26,38,57,9,49]
[3,41,52,26] [38,57,9,49]
[3,41] [52,26] [38,57] [9,49]
[3] [41] [52] [26] [38] [57] [9] [49] 這里是極限狀態(tài)，接下來就是merge的環(huán)節(jié)
[3,41] [26,52] [38,57] [9,49]
[3,26,41,52] [9,38,49,57]
[3,9,26,38,41,49,52,57]
2.3-2 重寫MERGE屑宠，使之不用哨兵厢洞，而是一旦數(shù)組L或者R的所有元素均被復制回A就立刻停止，然后把另一個數(shù)組的剩余部分復制回A。
void merge(std::vector<int>& A, int begin, int middle, int end)
{
std::vector<int> temp = A;
int i = begin;
int j = middle + 1;
for (int k = begin; k <= end; ++k) {
if (i > middle) A[k] = temp[j++];
else if (j > end) A[k] = temp[i++];
else if (temp[i] < temp[j]) A[k] = temp[i++];
else A[k] = temp[j++];
}
}
2.3-3 2.3-4 TODO
2.3-5 回顧查找問題躺翻，注意到丧叽，如果序列A已經(jīng)排好序，就可以將該序列的中點與v進行比較公你。根據(jù)比較的結果踊淳，原序列中有一半就可以不用再做進一步考慮了。二分查找算法重復這個過程陕靠，每次都將序列剩余部分的規(guī)模減半迂尝。為二分查找寫出迭代或者遞歸的偽代碼。證明：二分查找的最壞情況運行時間為Θ(nlgn)剪芥。
int binary_search(std::vector<int>& A, int val)
{
int begin = 0;
int end = A.size() - 1;
while (begin < end) {
int mid = begin + (end - begin) / 2;
if (val < A[mid]) end = mid - 1;
else if (val > A[mid]) begin = mid + 1;
else return mid;
}
return -1;
}
2.3-6 我們可以使用二分查找來把插入排序的最壞情況總運行時間改進到Θ(nlgn)嗎垄开？
在鏈表上可以做到，但是在線性表上是不行的税肪，因為線性表的插入總是需要和數(shù)組長度為線性關系的時間溉躲。
2.3-7 TODO
