第3章 排序與查找
在計算機科學(xué)中，排序(sorting)是研究得最多的問題之一，許多書籍都深入討論了這個問題。本章僅僅是一個介紹，重點放在C語言的實際應(yīng)用上。
排 序
程序員可以使用的基本排序算法有5種：
·插入排序(insertionsort．)
·交換排序(exchangesOrt)
·選擇排序(selectionsort)
·歸并排序(mergesort)
·分布排序(distributionsort)
為了形象地解釋每種排序算法是怎樣工作的，讓我們來看一看怎樣用這些方法對桌上一付亂序的牌進行排序。牌既要按花色排序(依次為梅花、方塊、紅桃和黑心)，還要按點數(shù)排序(從2到A)。
插入排序的過程為：從一堆牌的上面開始拿牌，每次拿一張牌，按排序原則把牌放到手中正確的位置。桌上的牌拿完后，手中的牌也就排好序了。
交換排序的過程為：
(1)先拿兩張牌放到手中。如果左邊的牌要排在右邊的牌的后面，就交換這兩張牌的位置。
(2)然后拿下一張牌，并比較最右邊兩張牌，如果有必要就交換這兩張牌的位置。
(3)重復(fù)第(2)步，直到把所有的牌都拿到手中。
(4)如果不再需要交換手中任何兩張牌的位置，就說明牌已經(jīng)排好序了；否則，把手中的牌放到桌上，重復(fù)(1)至(4)步，直到手中的牌排好序。
選擇排序的過程為：在桌上的牌中找出最小的一張牌，拿在手中；重復(fù)這種操作，直到把所有牌都拿在手中。
歸并排序的過程為：把桌上的牌分為52堆，每堆為一張牌。因為每堆牌都是有序的(記住，此時每堆中只有一張牌)，所以如果把相鄰的兩堆牌合并為一堆，并對每堆牌進行排序，就可以得到26堆已排好序的牌，此時每一堆中有兩張牌。重復(fù)這種合并操作，就可以依次得到13堆牌(每一堆中有4張牌)，7堆牌(有6堆是8張牌，還有一堆是4張牌)，最后將得到52張的一堆牌。
分布排序(也被稱作radix sort，即基數(shù)排序)的過程為：先將牌按點數(shù)分成13堆，然后將這13堆牌按點數(shù)順序疊在一起；再將牌按花色分成4堆，然后將這4堆牌按花色順序疊在一起，牌就排好序了。
在選用排序算法時，你還需要了解以下幾個術(shù)語：
(1)自然的(natural)
如果某種排序算法對有序的數(shù)據(jù)排序速度較快(工作量變小)，對無序的數(shù)據(jù)排序速度卻較慢(工作變量大)，我們就稱這種排序算法是自然的。如果數(shù)據(jù)已接近有序，就需要考慮選用自然的排序算法。
(2)穩(wěn)定的(stable)
如果某種排序算法能保持它認為相等的數(shù)據(jù)的前后順序，我們就稱這種排序算法是穩(wěn)定的。
例如，現(xiàn)有以下名單：
Mary Jones
Mary Smith
Tom Jones
Susie Queue
如果用穩(wěn)定的排序算法按姓對上述名單進行排序，那么在排好序后"Mary Jones”和"Tom Jones”將保持原來的Jr順序，因為它們的姓是相同的。
穩(wěn)定的排序算法可按主、次關(guān)鍵字對數(shù)據(jù)進行排序，例如按姓和名排序(換句話說，主要按姓排序，但對姓相同的數(shù)據(jù)還要按名排序)。在具體實現(xiàn)時，就是先按次關(guān)鍵字排序，再按主關(guān)鍵字排序。
(3)內(nèi)部排序(internal sort)和外部排序(external sort)
待排數(shù)據(jù)全部在內(nèi)存中的排序方法被稱為內(nèi)部排序，待排數(shù)據(jù)在磁盤、磁帶和其它外存中的排序方法被稱為外部排序。
查 找
和排序算法一樣，查找(searching)算法也是計算機科學(xué)中研究得最多的問題之一。查找算法和排序算法是有聯(lián)系的，因為許多查找算法依賴于要查找的數(shù)據(jù)集的有序程度?；镜牟檎宜惴ㄓ幸韵?種：
·順序查找(sequential searching)。
·比較查找(comparison searching)
·基數(shù)查找(radix searching)
·哈希查找(hashing)
下面仍然以一付亂序的牌為例來描述這些算法的工作過程。
順序查找的過程為：從第一張開始查看每一張牌，直到找到要找的牌。
比較查找(也被稱作binarysearching，即折半查找)要求牌已經(jīng)排好序，其過程為：任意抽一張牌，如果這張牌正是要找的牌，則查找過程結(jié)束。如果抽出的這張牌比要找的牌大，則在它前面的牌中重復(fù)查找操作；反之，則在它后面的牌中重復(fù)查找操作，直到找到要找的牌。
在計算機科學(xué)中，排序(sorting)是研究得最多的問題之一，許多書籍都深入討論了這個問題。本章僅僅是一個介紹，重點放在C語言的實際應(yīng)用上。
排 序
程序員可以使用的基本排序算法有5種：
·插入排序(insertionsort．)
·交換排序(exchangesOrt)
·選擇排序(selectionsort)
·歸并排序(mergesort)
·分布排序(distributionsort)
為了形象地解釋每種排序算法是怎樣工作的，讓我們來看一看怎樣用這些方法對桌上一付亂序的牌進行排序。牌既要按花色排序(依次為梅花、方塊、紅桃和黑心)，還要按點數(shù)排序(從2到A)。
插入排序的過程為：從一堆牌的上面開始拿牌，每次拿一張牌，按排序原則把牌放到手中正確的位置。桌上的牌拿完后，手中的牌也就排好序了。
交換排序的過程為：
(1)先拿兩張牌放到手中。如果左邊的牌要排在右邊的牌的后面，就交換這兩張牌的位置。
(2)然后拿下一張牌，并比較最右邊兩張牌，如果有必要就交換這兩張牌的位置。
(3)重復(fù)第(2)步，直到把所有的牌都拿到手中。
(4)如果不再需要交換手中任何兩張牌的位置，就說明牌已經(jīng)排好序了；否則，把手中的牌放到桌上，重復(fù)(1)至(4)步，直到手中的牌排好序。
選擇排序的過程為：在桌上的牌中找出最小的一張牌，拿在手中；重復(fù)這種操作，直到把所有牌都拿在手中。
歸并排序的過程為：把桌上的牌分為52堆，每堆為一張牌。因為每堆牌都是有序的(記住，此時每堆中只有一張牌)，所以如果把相鄰的兩堆牌合并為一堆，并對每堆牌進行排序，就可以得到26堆已排好序的牌，此時每一堆中有兩張牌。重復(fù)這種合并操作，就可以依次得到13堆牌(每一堆中有4張牌)，7堆牌(有6堆是8張牌，還有一堆是4張牌)，最后將得到52張的一堆牌。
分布排序(也被稱作radix sort，即基數(shù)排序)的過程為：先將牌按點數(shù)分成13堆，然后將這13堆牌按點數(shù)順序疊在一起；再將牌按花色分成4堆，然后將這4堆牌按花色順序疊在一起，牌就排好序了。
在選用排序算法時，你還需要了解以下幾個術(shù)語：
(1)自然的(natural)
如果某種排序算法對有序的數(shù)據(jù)排序速度較快(工作量變小)，對無序的數(shù)據(jù)排序速度卻較慢(工作變量大)，我們就稱這種排序算法是自然的。如果數(shù)據(jù)已接近有序，就需要考慮選用自然的排序算法。
(2)穩(wěn)定的(stable)
如果某種排序算法能保持它認為相等的數(shù)據(jù)的前后順序，我們就稱這種排序算法是穩(wěn)定的。
例如，現(xiàn)有以下名單：
Mary Jones
Mary Smith
Tom Jones
Susie Queue
如果用穩(wěn)定的排序算法按姓對上述名單進行排序，那么在排好序后"Mary Jones”和"Tom Jones”將保持原來的Jr順序，因為它們的姓是相同的。
穩(wěn)定的排序算法可按主、次關(guān)鍵字對數(shù)據(jù)進行排序，例如按姓和名排序(換句話說，主要按姓排序，但對姓相同的數(shù)據(jù)還要按名排序)。在具體實現(xiàn)時，就是先按次關(guān)鍵字排序，再按主關(guān)鍵字排序。
(3)內(nèi)部排序(internal sort)和外部排序(external sort)
待排數(shù)據(jù)全部在內(nèi)存中的排序方法被稱為內(nèi)部排序，待排數(shù)據(jù)在磁盤、磁帶和其它外存中的排序方法被稱為外部排序。
查 找
和排序算法一樣，查找(searching)算法也是計算機科學(xué)中研究得最多的問題之一。查找算法和排序算法是有聯(lián)系的，因為許多查找算法依賴于要查找的數(shù)據(jù)集的有序程度?；镜牟檎宜惴ㄓ幸韵?種：
·順序查找(sequential searching)。
·比較查找(comparison searching)
·基數(shù)查找(radix searching)
·哈希查找(hashing)
下面仍然以一付亂序的牌為例來描述這些算法的工作過程。
順序查找的過程為：從第一張開始查看每一張牌，直到找到要找的牌。
比較查找(也被稱作binarysearching，即折半查找)要求牌已經(jīng)排好序，其過程為：任意抽一張牌，如果這張牌正是要找的牌，則查找過程結(jié)束。如果抽出的這張牌比要找的牌大，則在它前面的牌中重復(fù)查找操作；反之，則在它后面的牌中重復(fù)查找操作，直到找到要找的牌。