# 第?11?章?排序與查找
**目錄**
+ [1\. 算法的概念](ch11s01.html)
+ [2\. 插入排序](ch11s02.html)
+ [3\. 算法的時間復雜度分析](ch11s03.html)
+ [4\. 歸并排序](ch11s04.html)
+ [5\. 線性查找](ch11s05.html)
+ [6\. 折半查找](ch11s06.html)
## 1.?算法的概念
算法(Algorithm)是將一組輸入轉化成一組輸出的一系列計算步驟,其中每個步驟必須能在有限時間內完成。比如[第?3?節 “遞歸”](ch05s03.html#func2.recursion)習題1中的Euclid算法,輸入是兩個正整數,輸出是它們的最大公約數,計算步驟是取模、比較等操作,這個算法一定能在有限的步驟和時間內完成(想一想為什么?)。再比如將一組數從小到大排序,輸入是一組原始數據,輸出是排序之后的數據,計算步驟包括比較、移動數據等操作。
算法是用來解決一類計算問題的,注意是一類問題,而不是一個特定的問題。例如,一個排序算法應該能對任意一組數據進行排序,而不是僅對`int a[] = { 1, 3, 4, 2, 6, 5 };`這樣一組數據排序,如果只需要對這一組數據排序可以寫這樣一個函數來做:
```
void sort(void)
{
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
a[5] = 6;
}
```
這顯然不叫算法,因為不具有通用性。由于算法是用來解決一類問題的,它必須能夠正確地解決這一類問題中的任何一個實例,這個算法才是正確的。對于排序算法,任意輸入一組數據,它必須都能輸出正確的排序結果,這個排序算法才是正確的。不正確的算法有兩種可能,一是對于該問題的某些輸入,該算法會無限計算下去,不會終止,二是對于該問題的某些輸入,該算法終止時輸出的是錯誤的結果。有時候不正確的算法也是有用的,如果對于某個問題尋求正確的算法很困難,而某個不正確的算法可以在有限時間內終止,并且能把誤差控制在一定范圍內,那么這樣的算法也是有實際意義的。例如有時候尋找最優解的開銷很大,往往會選擇能給出次優解的算法。
本章介紹幾種典型的排序和查找算法,并圍繞這幾種算法做時間復雜度分析。學完本章之后如果想進一步學習,可以參考一些全面系統地介紹算法的書,例如[[TAOCP]](bi01.html#bibli.taocp "The Art of Computer Programming")和[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。
## 2.?插入排序
插入排序算法類似于玩撲克時抓牌的過程,玩家每拿到一張牌都要插入到手中已有的牌里,使之從小到大排好序。例如(該圖出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")):
**圖?11.1.?撲克牌的插入排序**

也許你沒有意識到,但其實你的思考過程是這樣的:現在抓到一張7,把它和手里的牌從右到左依次比較,7比10小,應該再往左插,7比5大,好,就插這里。為什么比較了10和5就可以確定7的位置?為什么不用再比較左邊的4和2呢?因為這里有一個重要的前提:手里的牌已經是排好序的。現在我插了7之后,手里的牌仍然是排好序的,下次再抓到的牌還可以用這個方法插入。
編程對一個數組進行插入排序也是同樣道理,但和插入撲克牌有一點不同,不可能在兩個相鄰的存儲單元之間再插入一個單元,因此要將插入點之后的數據依次往后移動一個單元。排序算法如下:
**例?11.1.?插入排序**
```
#include <stdio.h>
#define LEN 5
int a[LEN] = { 10, 5, 2, 4, 7 };
void insertion_sort(void)
{
int i, j, key;
for (j = 1; j < LEN; j++) {
printf("%d, %d, %d, %d, %d\n",
a[0], a[1], a[2], a[3], a[4]);
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key) {
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
printf("%d, %d, %d, %d, %d\n",
a[0], a[1], a[2], a[3], a[4]);
}
int main(void)
{
insertion_sort();
return 0;
}
```
為了更清楚地觀察排序過程,我們在每次循環開頭插了打印語句,在排序結束后也插了打印語句。程序運行結果是:
```
_10_, 5, 2, 4, 7
_5, 10_, 2, 4, 7
_2, 5, 10_, 4, 7
_2, 4, 5, 10_, 7
_2, 4, 5, 7, 10_
```
如何嚴格證明這個算法是正確的?換句話說,只要反復執行該算法的`for`循環體,執行`LEN-1`次,就一定能把數組`a`排好序,而不管數組`a`的原始數據是什么,如何證明這一點呢?我們可以借助Loop Invariant的概念和數學歸納法來理解循環結構的算法,假如某個判斷條件滿足以下三條準則,它就稱為Loop Invariant:
1. 第一次執行循環體之前該判斷條件為真。
2. 如果“第N-1次循環之后(或者說第N次循環之前)該判斷條件為真”這個前提可以成立,那么就有辦法證明第N次循環之后該判斷條件仍為真。
3. 如果在所有循環結束后該判斷條件為真,那么就有辦法證明該算法正確地解決了問題。
只要我們找到這個Loop Invariant,就可以證明一個循環結構的算法是正確的。上述插入排序算法的Loop Invariant是這樣的判斷條件:_第`j`次循環之前,子序列a[0..j-1]是排好序的_。在上面的打印結果中,我把子序列a[0..j-1]加粗表示。下面我們驗證一下Loop Invariant的三條準則:
1. 第一次執行循環之前,`j=1`,子序列a[0..j-1]只有一個元素`a[0]`,只有一個元素的序列顯然是排好序的。
2. 第`j`次循環之前,如果“子序列a[0..j-1]是排好序的”這個前提成立,現在要把`key=a[j]`插進去,按照該算法的步驟,把`a[j-1]`、`a[j-2]`、`a[j-3]`等等比`key`大的元素都依次往后移一個,直到找到合適的位置給`key`插入,就能證明循環結束時子序列a[0..j]是排好序的。就像插撲克牌一樣,“手中已有的牌是排好序的”這個前提很重要,如果沒有這個前提,就不能證明再插一張牌之后也是排好序的。
3. 當循環結束時,`j=LEN`,如果“子序列a[0..j-1]是排好序的”這個前提成立,那就是說a[0..LEN-1]是排好序的,也就是說整個數組`a`的`LEN`個元素都排好序了。
可見,有了這三條,就可以用數學歸納法證明這個循環是正確的。這和[第?3?節 “遞歸”](ch05s03.html#func2.recursion)證明遞歸程序正確性的思想是一致的,這里的第一條就相當于遞歸的Base Case,第二條就相當于遞歸的遞推關系。這再次說明了遞歸和循環是等價的。
## 3.?算法的時間復雜度分析
解決同一個問題可以有很多種算法,比較評價算法的好壞,一個重要的標準就是算法的時間復雜度。現在研究一下插入排序算法的執行時間,按照習慣,輸入長度`LEN`以下用n表示。設循環中各條語句的執行時間分別是c1、c2、c3、c4、c5這樣五個常數<sup>[[23](#ftn.id2745592)]</sup>:
```
void insertion_sort(void) 執行時間
{
int i, j, key;
for (j = 1; j < LEN; j++) {
key = a[j]; c1
i = j - 1; c2
while (i >= 0 && a[i] > key) {
a[i+1] = a[i]; c3
i--; c4
}
a[i+1] = key; c5
}
}
```
顯然外層`for`循環的執行次數是n-1次,假設內層的`while`循環執行m次,則總的執行時間粗略估計是(n-1)*(c1+c2+c5+m*(c3+c4))。當然,`for`和`while`后面()括號中的賦值和條件判斷的執行也需要時間,而我沒有設一個常數來表示,這不影響我們的粗略估計。
這里有一個問題,m不是個常數,也不取決于輸入長度n,而是取決于具體的輸入數據。在最好情況下,數組`a`的原始數據已經排好序了,`while`循環一次也不執行,總的執行時間是(c1+c2+c5)*n-(c1+c2+c5),可以表示成an+b的形式,是n的線性函數(Linear Function)。那么在最壞情況(Worst Case)下又如何呢?所謂最壞情況是指數組`a`的原始數據正好是從大到小排好序的,請讀者想一想為什么這是最壞情況,然后把上式中的m替換掉算一下執行時間是多少。
數組`a`的原始數據屬于最好和最壞情況的都比較少見,如果原始數據是隨機的,可稱為平均情況(Average Case)。如果原始數據是隨機的,那么每次循環將已排序的子序列a[1..j-1]與新插入的元素`key`相比較,子序列中平均都有一半的元素比`key`大而另一半比`key`小,請讀者把上式中的m替換掉算一下執行時間是多少。最后的結論應該是:在最壞情況和平均情況下,總的執行時間都可以表示成an<sup>2</sup>+bn+c的形式,是n的二次函數(Quadratic Function)。
在分析算法的時間復雜度時,我們更關心最壞情況而不是最好情況,理由如下:
1. 最壞情況給出了算法執行時間的上界,我們可以確信,無論給什么輸入,算法的執行時間都不會超過這個上界,這樣為比較和分析提供了便利。
2. 對于某些算法,最壞情況是最常發生的情況,例如在數據庫中查找某個信息的算法,最壞情況就是數據庫中根本不存在該信息,都找遍了也沒有,而某些應用場合經常要查找一個信息在數據庫中存在不存在。
3. 雖然最壞情況是一種悲觀估計,但是對于很多問題,平均情況和最壞情況的時間復雜度差不多,比如插入排序這個例子,平均情況和最壞情況的時間復雜度都是輸入長度n的二次函數。
比較兩個多項式a<sub>1</sub>n+b<sub>1</sub>和a<sub>2</sub>n<sup>2</sup>+b<sub>2</sub>n+c<sub>2</sub>的值(n取正整數)可以得出結論:n的最高次指數是最主要的決定因素,常數項、低次冪項和系數都是次要的。比如100n+1和n<sup>2</sup>+1,雖然后者的系數小,當n較小時前者的值較大,但是當n>100時,后者的值就遠遠大于前者了。如果同一個問題可以用兩種算法解決,其中一種算法的時間復雜度為線性函數,另一種算法的時間復雜度為二次函數,當問題的輸入長度n足夠大時,前者明顯優于后者。因此我們可以用一種更粗略的方式表示算法的時間復雜度,把系數和低次冪項都省去,線性函數記作Θ(n),二次函數記作Θ(n<sup>2</sup>)。
Θ(g(n))表示和g(n)同一量級的一類函數,例如所有的二次函數f(n)都和g(n)=n<sup>2</sup>屬于同一量級,都可以用Θ(n<sup>2</sup>)來表示,甚至有些不是二次函數的也和n<sup>2</sup>屬于同一量級,例如2n<sup>2</sup>+3lgn。“同一量級”這個概念可以用下圖來說明(該圖出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")):
**圖?11.2.?Θ-notation**

如果可以找到兩個正的常數c<sub>1</sub>和c<sub>2</sub>,使得n足夠大的時候(也就是n≥n<sub>0</sub>的時候)f(n)總是夾在c<sub>1</sub>g(n)和c<sub>2</sub>g(n)之間,就說f(n)和g(n)是同一量級的,f(n)就可以用Θ(g(n))來表示。
以二次函數為例,比如1/2n<sup>2</sup>-3n,要證明它是屬于Θ(n<sup>2</sup>)這個集合的,我們必須確定c<sub>1</sub>、c<sub>2</sub>和n<sub>0</sub>,這些常數不隨n改變,并且當n≥n<sub>0</sub>以后,c<sub>1</sub>n<sup>2</sup>≤1/2n<sup>2</sup>-3n≤c<sub>2</sub>n<sup>2</sup>總是成立的。為此我們從不等式的每一邊都除以n<sup>2</sup>,得到c<sub>1</sub>≤1/2-3/n≤c<sub>2</sub>。見下圖:
**圖?11.3.?1/2-3/n**

這樣就很容易看出來,無論n取多少,該函數一定小于1/2,因此c<sub>2</sub>=1/2,當n=6時函數值為0,n>6時該函數都大于0,可以取n<sub>0</sub>=7,c<sub>1</sub>=1/14,這樣當n≥n<sub>0</sub>時都有1/2-3/n≥c<sub>1</sub>。通過這個證明過程可以得出結論,當n足夠大時任何an<sup>2</sup>+bn+c都夾在c<sub>1</sub>n<sup>2</sup>和c<sub>2</sub>n<sup>2</sup>之間,相對于n<sup>2</sup>項來說bn+c的影響可以忽略,a可以通過選取合適的c<sub>1</sub>、c<sub>2</sub>來補償。
幾種常見的時間復雜度函數按數量級從小到大的順序依次是:Θ(lgn),Θ(sqrt(n)),Θ(n),Θ(nlgn),Θ(n<sup>2</sup>),Θ(n<sup>3</sup>),Θ(2<sup>n</sup>),Θ(n!)。其中,lgn通常表示以10為底n的對數,但是對于Θ-notation來說,Θ(lgn)和Θ(log<sub>2</sub>n)并無區別(想一想這是為什么),在算法分析中lgn通常表示以2為底n的對數。可是什么算法的時間復雜度里會出現lgn呢?回顧插入排序的時間復雜度分析,無非是循環體的執行時間乘以循環次數,只有加和乘運算,怎么會出來lg呢?下一節歸并排序的時間復雜度里面就有lg,請讀者留心lg運算是從哪出來的。
除了Θ-notation之外,表示算法的時間復雜度常用的還有一種Big-O notation。我們知道插入排序在最壞情況和平均情況下時間復雜度是Θ(n<sup>2</sup>),在最好情況下是Θ(n),數量級比Θ(n<sup>2</sup>)要小,那么總結起來在各種情況下插入排序的時間復雜度是O(n<sup>2</sup>)。Θ的含義和“等于”類似,而大O的含義和“小于等于”類似。
* * *
<sup>[[23](#id2745592)]</sup> 受內存管理機制的影響,指令的執行時間不一定是常數,但執行時間的上界(Upper Bound)肯定是常數,我們這里假設語句的執行時間是常數只是一個粗略估計。
## 4.?歸并排序
插入排序算法采取增量式(Incremental)的策略解決問題,每次添一個元素到已排序的子序列中,逐漸將整個數組排序完畢,它的時間復雜度是O(n<sup>2</sup>)。下面介紹另一種典型的排序算法--歸并排序,它采取分而治之(Divide-and-Conquer)的策略,時間復雜度是Θ(nlgn)。歸并排序的步驟如下:
1. Divide: 把長度為n的輸入序列分成兩個長度為n/2的子序列。
2. Conquer: 對這兩個子序列分別采用歸并排序。
3. Combine: 將兩個排序好的子序列合并成一個最終的排序序列。
在描述歸并排序的步驟時又調用了歸并排序本身,可見這是一個遞歸的過程。
**例?11.2.?歸并排序**
```
#include <stdio.h>
#define LEN 8
int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 };
void merge(int start, int mid, int end)
{
int n1 = mid - start + 1;
int n2 = end - mid;
int left[n1], right[n2];
int i, j, k;
for (i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i] = a[start+i];
for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j] = a[mid+1+j];
i = j = 0;
k = start;
while (i < n1 && j < n2)
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
while (i < n1) /* left[] is not exhausted */
a[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */
a[k++] = right[j++];
}
void sort(int start, int end)
{
int mid;
if (start < end) {
mid = (start + end) / 2;
printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n",
start, mid, mid+1, end,
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
sort(start, mid);
sort(mid+1, end);
merge(start, mid, end);
printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n",
start, mid, mid+1, end,
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
}
}
int main(void)
{
sort(0, LEN-1);
return 0;
}
```
執行結果是:
```
sort (0-3, 4-7) 5 2 4 7 1 3 2 6
sort (0-1, 2-3) 5 2 4 7 1 3 2 6
sort (0-0, 1-1) 5 2 4 7 1 3 2 6
merge (0-0, 1-1) to 2 5 4 7 1 3 2 6
sort (2-2, 3-3) 2 5 4 7 1 3 2 6
merge (2-2, 3-3) to 2 5 4 7 1 3 2 6
merge 0-1, 2-3) to 2 4 5 7 1 3 2 6
sort (4-5, 6-7) 2 4 5 7 1 3 2 6
sort (4-4, 5-5) 2 4 5 7 1 3 2 6
merge (4-4, 5-5) to 2 4 5 7 1 3 2 6
sort (6-6, 7-7) 2 4 5 7 1 3 2 6
merge (6-6, 7-7) to 2 4 5 7 1 3 2 6
merge (4-5, 6-7) to 2 4 5 7 1 2 3 6
merge (0-3, 4-7) to 1 2 2 3 4 5 6 7
```
`sort`函數把a[start..end]平均分成兩個子序列,分別是a[start..mid]和a[mid+1..end],對這兩個子序列分別遞歸調用`sort`函數進行排序,然后調用`merge`函數將排好序的兩個子序列合并起來,由于兩個子序列都已經排好序了,合并的過程很簡單,每次循環取兩個子序列中最小的元素進行比較,將較小的元素取出放到最終的排序序列中,如果其中一個子序列的元素已取完,就把另一個子序列剩下的元素都放到最終的排序序列中。為了便于理解程序,我在`sort`函數開頭和結尾插了打印語句,可以看出調用過程是這樣的:
**圖?11.4.?歸并排序調用過程**

圖中S表示`sort`函數,M表示`merge`函數,整個控制流程沿虛線所示的方向調用和返回。由于`sort`函數遞歸調用了自己兩次,所以各函數之間的調用關系呈樹狀結構。畫這個圖只是為了清楚地展現歸并排序的過程,讀者在理解遞歸函數時一定不要全部展開來看,而是要抓住Base Case和遞推關系來理解。我們分析一下歸并排序的時間復雜度,以下分析出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。
首先分析`merge`函數的時間復雜度。在`merge`函數中演示了C99的新特性--可變長數組,當然也可以避免使用這一特性,比如把`left`和`right`都按最大長度`LEN`分配。不管用哪種辦法,定義數組并分配存儲空間的執行時間都可以看作常數,與數組的長度無關,常數用Θ-notation記作Θ(1)。設子序列a[start..mid]的長度為`n1`,子序列[mid+1..end]的長度為`n2`,a[start..end]的總長度為n=n1+n2,則前兩個`for`循環的執行時間是Θ(n1+n2),也就是Θ(n),后面三個`for`循環合在一起看,每走一次循環就會在最終的排序序列中確定一個元素,最終的排序序列共有n個元素,所以執行時間也是Θ(n)。兩個Θ(n)再加上若干常數項,`merge`函數總的執行時間仍是Θ(n),其中n=end-start+1。
然后分析`sort`函數的時間復雜度,當輸入長度n=1,也就是`start==end`時,`if`條件不成立,執行時間為常數Θ(1),當輸入長度n>1時:
總的執行時間?=?2?×?輸入長度為n/2的`sort`函數的執行時間?+?`merge`函數的執行時間Θ(n)
設輸入長度為n的`sort`函數的執行時間為T(n),綜上所述:

這是一個遞推公式(Recurrence),我們需要消去等號右側的T(n),把T(n)寫成n的函數。其實符合一定條件的Recurrence的展開有數學公式可以套,這里我們略去嚴格的數學證明,只是從直觀上看一下這個遞推公式的結果。當n=1時可以設T(1)=c<sub>1</sub>,當n>1時可以設T(n)=2T(n/2)+c<sub>2</sub>n,我們取c<sub>1</sub>和c<sub>2</sub>中較大的一個設為c,把原來的公式改為:

這樣計算出的結果應該是T(n)的上界。下面我們把T(n/2)展開成2T(n/4)+cn/2(下圖中的(c)),然后再把T(n/4)進一步展開,直到最后全部變成T(1)=c(下圖中的(d)):

把圖(d)中所有的項加起來就是總的執行時間。這是一個樹狀結構,每一層的和都是cn,共有lgn+1層,因此總的執行時間是cnlgn+cn,相比nlgn來說,cn項可以忽略,因此T(n)的上界是Θ(nlgn)。
如果先前取c<sub>1</sub>和c<sub>2</sub>中較小的一個設為c,計算出的結果應該是T(n)的下界,然而推導過程一樣,結果也是Θ(nlgn)。既然T(n)的上下界都是Θ(nlgn),顯然T(n)就是Θ(nlgn)。
和插入排序的平均情況相比歸并排序更快一些,雖然`merge`函數的步驟較多,引入了較大的常數、系數和低次項,但是對于較大的輸入長度n,這些都不是主要因素,歸并排序的時間復雜度是Θ(nlgn),而插入排序的平均情況是Θ(n<sup>2</sup>),這就決定了歸并排序是更快的算法。但是不是任何情況下歸并排序都優于插入排序呢?哪些情況適用插入排序而不適用歸并排序?留給讀者思考。
### 習題
1、快速排序是另外一種采用分而治之策略的排序算法,在平均情況下的時間復雜度也是Θ(nlgn),但比歸并排序有更小的時間常數。它的基本思想是這樣的:
```
int partition(int start, int end)
{
從a[start..end]中選取一個pivot元素(比如選a[start]為pivot);
在一個循環中移動a[start..end]的數據,將a[start..end]分成兩半,
使a[start..mid-1]比pivot元素小,a[mid+1..end]比pivot元素大,而a[mid]就是pivot元素;
return mid;
}
void quicksort(int start, int end)
{
int mid;
if (end > start) {
mid = partition(start, end);
quicksort(start, mid-1);
quicksort(mid+1, end);
}
}
```
請補完`partition`函數,這個函數有多種寫法,請選擇時間常數盡可能小的實現方法。想想快速排序在最好和最壞情況下的時間復雜度是多少?快速排序在平均情況下的時間復雜度分析起來比較復雜,有興趣的讀者可以參考[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。
## 5.?線性查找
有些查找問題要用時間復雜度為O(n)的算法來解決。例如寫一個`indexof`函數,從任意輸入字符串中找出某個字母的位置并返回這個位置,如果找不到就返回-1:
**例?11.3.?線性查找**
```
#include <stdio.h>
char a[]="hello world";
int indexof(char letter)
{
int i = 0;
while (a[i] != '\0') {
if (a[i] == letter)
return i;
i++;
}
return -1;
}
int main(void)
{
printf("%d %d\n", indexof('o'), indexof('z'));
return 0;
}
```
這個實現是最直觀和最容易想到的,但它是不是最快的算法呢?我們知道插入排序也比歸并排序更容易想到,但通常不如歸并排序快。那么現在這個問題--給定一個隨機排列的序列,找出其中某個元素的位置--有沒有比O(n)更快的算法?比如O(lgn)?請讀者思考一下。
### 習題
1、實現一個算法,在一組隨機排列的數中找出最小的一個。你能想到的最直觀的算法一定是Θ(n)的,想想有沒有比Θ(n)更快的算法?
2、在一組隨機排列的數中找出第二小的,這個問題比上一個稍復雜,你能不能想出Θ(n)的算法?
3、進一步泛化,在一組隨機排列的數中找出第k小的,這個元素稱為k-th Order Statistic。能想到的最直觀的算法肯定是先把這些數排序然后取第k個,時間復雜度和排序算法相同,可以是Θ(nlgn)。這個問題雖然比前兩個問題復雜,但它也有平均情況下時間復雜度是Θ(n)的算法,將上一節習題1的快速排序算法稍加修改就可以解決這個問題:
```
/* 從start到end之間找出第k小的元素 */
int order_statistic(int start, int end, int k)
{
用partition函數把序列分成兩半,中間的pivot元素是序列中的第i個;
if (k == i)
返回找到的元素;
else if (k > i)
從后半部分找出第k-i小的元素并返回;
else
從前半部分找出第k小的元素并返回;
}
```
請編程實現這個算法。
## 6.?折半查找
如果不是從一組隨機的序列里查找,而是從一組排好序的序列里找出某個元素的位置,則可以有更快的算法:
**例?11.4.?折半查找**
```
#include <stdio.h>
#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
while (start <= end) {
mid = (start + end) / 2;
if (a[mid] < number)
start = mid + 1;
else if (a[mid] > number)
end = mid - 1;
else
return mid;
}
return -1;
}
int main(void)
{
printf("%d\n", binarysearch(5));
return 0;
}
```
由于這個序列已經從小到大排好序了,每次取中間的元素和待查找的元素比較,如果中間的元素比待查找的元素小,就說明“如果待查找的元素存在,一定位于序列的后半部分”,這樣可以把搜索范圍縮小到后半部分,然后再次使用這種算法迭代。這種“每次將搜索范圍縮小一半”的思想稱為折半查找(Binary Search)。思考一下,這個算法的時間復雜度是多少?
這個算法的思想很簡單,不是嗎?可是[[編程珠璣]](bi01.html#bibli.pearls "Programming Pearls")上說作者在課堂上講完這個算法的思想然后讓學生寫程序,有90%的人寫出的程序中有各種各樣的Bug,讀者不信的話可以不看書自己寫一遍試試。這個算法容易出錯的地方很多,比如`mid = (start + end) / 2;`這一句,在數學概念上其實是`mid = ?(start + end) / 2?`,還有`start = mid + 1;`和`end = mid - 1;`,如果前者寫成了`start = mid;`或后者寫成了`end = mid;`那么很可能會導致死循環(想一想什么情況下會死循環)。
怎樣才能保證程序的正確性呢?在[第?2?節 “插入排序”](ch11s02.html#sortsearch.insertion)我們講過借助Loop Invariant證明循環的正確性,`binarysearch`這個函數的主體也是一個循環,它的Loop Invariant可以這樣描述:_待查找的元素`number`如果存在于數組`a`之中,那么一定存在于a[start..end]這個范圍之間,換句話說,在這個范圍之外的數組`a`的元素中一定不存在`number`這個元素_。以下為了書寫方便,我們把這句話表示成`mustbe(start, end, number)`。可以一邊看算法一邊做推理:
```
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
/* 假定a是排好序的 */
/* mustbe(start, end, number),因為a[start..end]就是整個數組a[0..LEN-1] */
while (start <= end) {
/* mustbe(start, end, number),因為一開始進入循環時是正確的,每次循環也都維護了這個條件 */
mid = (start + end) / 2;
if (a[mid] < number)
/* 既然a是排好序的,a[start..mid]應該都比number小,所以mustbe(mid+1, end, number) */
start = mid + 1;
/* 維護了mustbe(start, end, number) */
else if (a[mid] > number)
/* 既然a是排好序的,a[mid..end]應該都比number大,所以mustbe(start, mid-1, number) */
end = mid - 1;
/* 維護了mustbe(start, end, number) */
else
/* a[mid] == number,說明找到了 */
return mid;
}
/*
* mustbe(start, end, number)一直被循環維護著,到這里應該仍然成立,在a[start..end]范圍之外一定不存在number,
* 但現在a[start..end]是空序列,在這個范圍之外的正是整個數組a,因此整個數組a中都不存在number
*/
return -1;
}
```
注意這個算法有一個非常重要的前提--`a`是排好序的。缺了這個前提,“如果`a[mid] < number`,那么a[start..mid]應該都比`number`小”這一步推理就不能成立,這個函數就不能正確地完成查找。從更普遍的意義上說,函數的調用者(Caller)和函數的實現者(Callee,被調用者)之間訂立了一個契約(Contract),在調用函數之前,Caller要為Callee提供某些條件,比如確保`a`是排好序的,確保a[start..end]都是有效的數組元素而沒有訪問越界,這稱為Precondition,然后Callee對一些Invariant進行維護(Maintenance),這些Invariant保證了Callee在函數返回時能夠對Caller盡到某些義務,比如確保“如果`number`在數組`a`中存在,一定能找出來并返回它的位置,如果`number`在數組`a`中不存在,一定能返回-1”,這稱為Postcondition。如果每個函數的文檔都非常清楚地記錄了Precondition、Maintenance和Postcondition是什么,那么每個函數都可以獨立編寫和測試,整個系統就會易于維護。這種編程思想是由Eiffel語言的設計者Bertrand Meyer提出來的,稱為Design by Contract(DbC)。
測試一個函數是否正確需要把Precondition、Maintenance和Postcondition這三方面都測試到,比如`binarysearch`這個函數,即使它寫得非常正確,既維護了Invariant也保證了Postcondition,如果調用它的Caller沒有保證Precondition,最后的結果也還是錯的。我們編寫幾個測試用的Predicate函數,然后把相關的測試插入到`binarysearch`函數中:
**例?11.5.?帶有測試代碼的折半查找**
```
#include <stdio.h>
#include <assert.h>
#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
int is_sorted(void)
{
int i;
for (i = 1; i < LEN; i++)
if (a[i-1] > a[i])
return 0;
return 1;
}
int mustbe(int start, int end, int number)
{
int i;
for (i = 0; i < start; i++)
if (a[i] == number)
return 0;
for (i = end+1; i < LEN; i++)
if (a[i] == number)
return 0;
return 1;
}
int contains(int n)
{
int i;
for (i = 0; i < LEN; i++)
if (a[i] == n)
return 1;
return 0;
}
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
assert(is_sorted()); /* Precondition */
while (start <= end) {
assert(mustbe(start, end, number)); /* Maintenance */
mid = (start + end) / 2;
if (a[mid] < number)
start = mid + 1;
else if (a[mid] > number)
end = mid - 1;
else {
assert(mid >= start && mid <= end
&& a[mid] == number) /* Postcondition 1 */
return mid;
}
}
assert(!contains(number)); /* Postcondition 2 */
return -1;
}
int main(void)
{
printf("%d\n", binarysearch(5));
return 0;
}
```
`assert`是頭文件`assert.h`中的一個宏定義,執行到`assert(is_sorted())`這句時,如果`is_sorted()`返回值為真,則當什么事都沒發生過,繼續往下執行,如果`is_sorted()`返回值為假(例如把數組的排列順序改一改),則報錯退出程序:
```
main: main.c:33: binarysearch: Assertion `is_sorted()' failed.
Aborted
```
在代碼中適當的地方使用斷言(Assertion)可以有效地幫助我們測試程序。也許有人會問:我們用幾個測試函數來測試`binarysearch`,那么這幾個測試函數又用什么來測試呢?在實際工作中我們要測試的代碼絕不會像`binarysearch`這么簡單,而我們編寫的測試函數往往都很簡單,比較容易保證正確性,也就是用簡單的、不容易出錯的代碼去測試復雜的、容易出錯的代碼。
測試代碼只在開發和調試時有用,如果正式發布(Release)的軟件也要運行這些測試代碼就會嚴重影響性能了,如果在包含`assert.h`之前定義一個`NDEBUG`宏(表示No Debug),就可以禁用`assert.h`中的`assert`宏定義,這樣代碼中的所有`assert`測試都不起作用了:
```
#define NDEBUG
#include <stdio.h>
#include <assert.h>
...
```
注意`NDEBUG`和我們以前使用的宏定義有點不同,例如`#define N 20`將`N`定義為20,在預處理時把代碼中所有的標識符`N`替換成20,而`#define NDEBUG`把`NDEBUG`定義為空,在預處理時把代碼中所有的標識符`NDEBUG`替換成空。這樣的宏定義主要是為了用`#ifdef`等預處理指示測試它定義過沒有,而不是為了做替換,所以定義成什么值都無所謂,一般定義成空就足夠了。
還有另一種辦法,不必修改源文件,在編譯命令行加上選項`-DNDEBUG`就相當于在源文件開頭定義了`NDEBUG`宏。宏定義和預處理到[第?21?章 _預處理_](ch21.html#prep)再詳細解釋,在[第?4?節 “其它預處理特性”](ch21s04.html#prep.other)將給出`assert.h`一種實現。
### 習題
1、本節的折半查找算法有一個特點:如果待查找的元素在數組中有多個則返回其中任意一個,以本節定義的數組`int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };`為例,如果調用`binarysearch(2)`則返回3,即`a[3]`,而有些場合下要求這樣的查找返回`a[1]`,也就是說,如果待查找的元素在數組中有多個則返回第一個。請修改折半查找算法實現這一特性。
2、編寫一個函數`double mysqrt(double y);`求`y`的正平方根,參數`y`是正實數。我們用折半查找來找這個平方根,在從0到`y`之間必定有一個取值是`y`的平方根,如果我們查找的數`x`比`y`的平方根小,則x<sup>2</sup><y,如果我們查找的數`x`比`y`的平方根大,則x<sup>2</sup>>y,我們可以據此縮小查找范圍,當我們查找的數足夠準確時(比如滿足|x<sup>2</sup>-y|<0.001),就可以認為找到了`y`的平方根。思考一下這個算法需要迭代多少次?迭代次數的多少由什么因素決定?
3、編寫一個函數`double mypow(double x, int n);`求`x`的`n`次方,參數`n`是正整數。最簡單的算法是:
```
double product = 1;
for (i = 0; i < n; i++)
product *= x;
```
這個算法的時間復雜度是Θ(n)。其實有更好的辦法,比如`mypow(x, 8)`,第一次循環算出x·x=x<sup>2</sup>,第二次循環算出x<sup>2</sup>·x<sup>2</sup>=x<sup>4</sup>,第三次循環算出<sup>4</sup>·x<sup>4</sup>=x<sup>8</sup>。這樣只需要三次循環,時間復雜度是Θ(lgn)。思考一下如果`n`不是2的整數次冪應該怎么處理。請分別用遞歸和循環實現這個算法。
從以上幾題可以看出,折半查找的思想有非常廣泛的應用,不僅限于從一組排好序的元素中找出某個元素的位置,還可以解決很多類似的問題。[[編程珠璣]](bi01.html#bibli.pearls "Programming Pearls")對于折半查找的各種應用和優化技巧有非常詳細的介紹。
- Linux C編程一站式學習
- 歷史
- 前言
- 部分?I.?C語言入門
- 第?1?章?程序的基本概念
- 第?2?章?常量、變量和表達式
- 第?3?章?簡單函數
- 第?4?章?分支語句
- 第?5?章?深入理解函數
- 第?6?章?循環語句
- 第?7?章?結構體
- 第?8?章?數組
- 第?9?章?編碼風格
- 第?10?章?gdb
- 第?11?章?排序與查找
- 第?12?章?棧與隊列
- 第?13?章?本階段總結
- 部分?II.?C語言本質
- 第?14?章?計算機中數的表示
- 第?15?章?數據類型詳解
- 第?16?章?運算符詳解
- 第?17?章?計算機體系結構基礎
- 第?18?章?x86匯編程序基礎
- 第?19?章?匯編與C之間的關系
- 第?20?章?鏈接詳解
- 第?21?章?預處理
- 第?22?章?Makefile基礎
- 第?23?章?指針
- 第?24?章?函數接口
- 第?25?章?C標準庫
- 第?26?章?鏈表、二叉樹和哈希表
- 第?27?章?本階段總結
- 部分?III.?Linux系統編程
- 第?28?章?文件與I/O
- 第?29?章?文件系統
- 第?30?章?進程
- 第?31?章?Shell腳本
- 第?32?章?正則表達式
- 第?33?章?信號
- 第?34?章?終端、作業控制與守護進程
- 第?35?章?線程
- 第?36?章?TCP/IP協議基礎
- 第?37?章?socket編程
- 附錄?A.?字符編碼
- 附錄?B.?GNU Free Documentation License Version 1.3, 3 November 2008
- 參考書目
- 索引