程序員可以使用的基本排序算法有5種：
·插入排序(insertionsort．)
·交換排序(exchangesOrt)
·選擇排序(selectionsort)
·歸並排序(mergesort)
·分布排序(distributionsort)
為了形象地解釋每種排序算法是怎樣工作的，讓我們來看壹看怎樣用這些方法對桌上壹付亂序的牌進行排序。牌既要按花色排序(依次為梅花、方塊、紅桃和黑心)，還要按點數排序(從2到A)。
插入排序的過程為：從壹堆牌的上面開始拿牌，每次拿壹張牌，按排序原則把牌放到手中正確的位置。桌上的牌拿完後，手中的牌也就排好序了。
交換排序的過程為：
(1)先拿兩張牌放到手中。如果左邊的牌要排在右邊的牌的後面，就交換這兩張牌的位置。
(2)然後拿下壹張牌，並比較最右邊兩張牌，如果有必要就交換這兩張牌的位置。
(3)重復第(2)步，直到把所有的牌都拿到手中。
(4)如果不再需要交換手中任何兩張牌的位置，就說明牌已經排好序了；否則，把手中的牌放到桌上，重復(1)至(4)步，直到手中的牌排好序。
選擇排序的過程為：在桌上的牌中找出最小的壹張牌，拿在手中；重復這種操作，直到把所有牌都拿在手中。
歸並排序的過程為：把桌上的牌分為52堆，每堆為壹張牌。因為每堆牌都是有序的(記住，此時每堆中只有壹張牌)，所以如果把相鄰的兩堆牌合並為壹堆，並對每堆牌進行排序，就可以得到26堆已排好序的牌，此時每壹堆中有兩張牌。重復這種合並操作，就可以依次得到13堆牌(每壹堆中有4張牌)，7堆牌(有6堆是8張牌，還有壹堆是4張牌)，最後將得到52張的壹堆牌。
分布排序(也被稱作radix sort，即基數排序)的過程為：先將牌按點數分成13堆，然後將這13堆牌按點數順序疊在壹起；再將牌按花色分成4堆，然後將這4堆牌按花色順序疊在壹起，牌就排好序了。
在選用排序算法時，妳還需要了解以下幾個術語：
(1)自然的(natural)
如果某種排序算法對有序的數據排序速度較快(工作量變小)，對無序的數據排序速度卻較慢(工作變量大)，我們就稱這種排序算法是自然的。如果數據已接近有序，就需要考慮選用自然的排序算法。
(2)穩定的(stable)
如果某種排序算法能保持它認為相等的數據的前後順序，我們就稱這種排序算法是穩定的。
例如，現有以下名單：
Mary Jones
Mary Smith
Tom Jones
Susie Queue
如果用穩定的排序算法按姓對上述名單進行排序，那麽在排好序後"Mary Jones”和"Tom Jones”將保持原來的Jr順序，因為它們的姓是相同的。
穩定的排序算法可按主、次關鍵字對數據進行排序，例如按姓和名排序(換句話說，主要按姓排序，但對姓相同的數據還要按名排序)。在具體實現時，就是先按次關鍵字排序，再按主關鍵字排序。
(3)內部排序(internal sort)和外部排序(external sort)
待排數據全部在內存中的排序方法被稱為內部排序，待排數據在磁盤、磁帶和其它外存中的排序方法被稱為外部排序。
查 找：
和排序算法壹樣，查找(searching)算法也是計算機科學中研究得最多的問題之壹。查找算法和排序算法是有聯系的，因為許多查找算法依賴於要查找的數據集的有序程度。基本的查找算法有以下4種：
·順序查找(sequential searching)。
·比較查找(comparison searching)
·基數查找(radix searching)
·哈希查找(hashing)
下面仍然以壹付亂序的牌為例來描述這些算法的工作過程。
順序查找的過程為：從第壹張開始查看每壹張牌，直到找到要找的牌。
比較查找(也被稱作binarysearching，即折半查找)要求牌已經排好序，其過程為：任意抽壹張牌，如果這張牌正是要找的牌，則查找過程結束。如果抽出的這張牌比要找的牌大，則在它前面的牌中重復查找操作；反之，則在它後面的牌中重復查找操作，直到找到要找的牌。
基數查找的過程為：先將牌按點數分成13堆，或者按花色分成4堆。然後找出與要找的牌的點數或花色相同的那壹堆牌，再在這堆牌中用任意壹種查找算法找到要找的牌。
哈希查找的過程為：
(1)在桌面上留出可以放若幹堆牌的空間，並構造壹個函數，使其能根據點數和花色將牌映射到特定的堆中(這個函數被稱為hashfunction，即哈希函數)。
(2)根據哈希函數將牌分成若幹堆。
(3)根據哈希函數找到要找的牌所在的堆，然後在這壹堆牌中找到要找的牌。
例如，可以構造這樣壹個哈希函數：
pile=rank+suit
其中，rank是表示牌的點數的壹個數值；suit是表示牌的花色的壹個數值；pile表示堆值，它將決定壹張牌歸入到哪壹堆中。如果用1，2，……，13分別表示A，2，……．K，用0，1，2和3分別表示梅花、方塊、紅桃和黑桃，則pile的值將為1，2，……，16，這樣就可以把壹付牌分成16堆。
哈希查找雖然看上去有些離譜，但它確實是壹種非常實用的查找算法。各種各樣的程序，從壓縮程序(如Stacker)到磁盤高速緩存程序(如SmartDrive)，幾乎都通過這種方法來提高查找速度，
排序或查找的性能：
有關排序和查找的壹個主要問題就是速度。這個問題經常被人們忽視，因為與程序的其余部分相比，排序或查找所花費的時間幾乎可以被忽略。然而，對大多數排序或查找應用來說，妳不必壹開始就花很多精力去編制壹段算法程序，而應該先在現成的算法中選用壹種最簡單的(見3．1和3．4)，當妳發現所用的算法使程序運行很慢時，再換用壹種更好的算法(請參見下文中的介紹)。
下面介紹壹種判斷排序或查找算法的速度的方法。
首先，引入壹個算法的復雜度的概念，它指的是在各種情況(最好的、最差的和平均的)下排序或查找需要完成的操作次數，通過它可以比較不同算法的性能。
算法的復雜度與排序或查找所針對的數據集的數據量有關，因此，引入壹個基於數據集數據量的表達式來表示算法的復雜度。
最快的算法的復雜度O(1)，它表示算法的操作次數與數據量無關。復雜度O(N)(N表示數據集的數據量)表示算法的操作次數與數據量直接相關。復雜度O(logN)介於上述兩者之間，它表示算法的操作次數與數據量的對數有關。復雜度為O(NlogN)(N乘以logN)的算法比復雜度為O(N)的算法要慢，而復雜度為O(N2)的算法更慢。
註意：如果兩種算法的復雜度都是O(logN)，那麽logN的基數較大的算法的速度要快些，在本章的例子中，logN的基數均為10