國內最大的酷站演示中心!
算法是程序設計的精髓，程序設計的實質就是構造解決問題的算法，將其解釋為計算機語言。
在這里您可以了解到：
算法定義
偽代碼的使用
算法的復雜性
算法設計策略
常用算法
這里所有的算法都以一種類似pascal語言的偽代碼描述，請參閱偽代碼的使用。
新增內容
關于數(shù)論的算法——數(shù)論基本知識（may 6, 2001）
動態(tài)規(guī)劃重新整理 （january 15, 2001）
圖的深度優(yōu)先遍歷 （january 21, 2001）
圖的廣度優(yōu)先遍歷 （january 21, 2001）
圖的拓撲排序 （january 21, 2001）
算法 algorithm
算法是在有限步驟內求解某一問題所使用的一組定義明確的規(guī)則。通俗點說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。
一個算法應該具有以下五個重要的特征：
1. 有窮性： 一個算法必須保證執(zhí)行有限步之后結束；
2. 確切性： 算法的每一步驟必須有確切的定義；
3. 輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件；
4. 輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果。沒有輸出的算法是毫無意義的；
5. 可行性： 算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。
did you know
algorithm 一詞的由來
algorithm(算法)一詞本身就十分有趣。初看起來，這個詞好像是某人打算要寫“l(fā)ogarithm”(對數(shù))一詞但卻把頭四個字母寫的前后顛倒了。這個詞一直到1957年之前在webster's new world dictionary(《韋氏新世界詞典》)中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“algorism”(算術)，指的是用阿拉伯數(shù)字進行算術運算的過程。在中世紀時，珠算家用算盤進行計算，而算術家用算術進行計算。中世紀之后，對這個詞的起源已經拿不準了，早期的語言學家試圖推斷它的來歷，認為它是從把algiros(費力的)+arithmos(數(shù)字)組合起來派生而成的，但另一些人則不同意這種說法，認為這個詞是從“喀斯迪爾國王algor”派生而來的。最后，數(shù)學史學家發(fā)現(xiàn)了algorism(算術)一詞的真實起源：它來源于著名的persian textbook(《波斯教科書》)的作者的名字abu ja'far mohammed ibn mûsâ al-khowârizm （約公元前825年）——從字面上看，這個名字的意思是“ja'far 的父親，mohammed 和 mûsâ 的兒子，khowârizm 的本地人”。khowârizm 是前蘇聯(lián)xиba(基發(fā)) 的小城鎮(zhèn) 。al-khowârizm 寫了著名的書kitab al jabr w'al-muqabala (《復原和化簡的規(guī)則》)；另一個詞，“algebra”(代數(shù))，是從他的書的標題引出來的，盡管這本書實際上根本不是講代數(shù)的。
逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語字典所說明的，這個詞是由于同arithmetic(算術)相混淆而形成的錯拼詞。由algorism又變成algorithm。一本早期的德文數(shù)學詞典 vollstandiges mathematisches lexicon (《數(shù)學大全辭典》) ，給出了algorithmus (算法)一詞的如下定義：“在這個名稱之下，組合了四種類型的算術計算的概念，即加法、乘法、減法、除法”。拉頂短語algorithmus infinitesimalis (無限小方法) ，在當時就用來表示leibnitz(萊布尼茲)所發(fā)明的以無限小量進行計算的微積分方法。
1950年左右，algorithm一詞經常地同歐幾里德算法(euclid's algorithm)聯(lián)系在一起。這個算法就是在歐幾里德的《幾何原本》(euclid's elements ,第vii卷，命題i和ii)中所闡述的求兩個數(shù)的最大公約數(shù)的過程(即輾轉相除法)。
左上方的圖片是abu ja'far mohammed ibn mûsâ al-khowârizm的肖像，點擊該圖片可以看見關于他的更詳細的資料。
排序
sorting
排序問題的輸入是一個線性表，該線性表的元素屬于一個偏序集；要求對該線性表的元素做某種重排，使得線性表中除表尾外的每個元素都小于等于（或大于等于）它的后繼。
設r為非空集合a上的二元關系，如果r滿足自反性(對于每一個x∈a，(x,x)∈r )，反對稱性((x,y)∈r∧(y,x)∈r→x=y )和傳遞性((x,y)∈r∧(y,x)∈r→(x,z)∈r)，則稱r為a上的偏序關系，記作≤。如果(x,y)∈r，則記作x≤y，讀作“x小于等于y”。存在偏序關系的集合a稱為偏序集。
注意，這里的≤不是指數(shù)的大小，而是指在偏序關系中的順序性。x≤y的含義是：按照這個序，x排在y前面。根據(jù)不同的偏序定義，≤有不同的解釋。例如整除關系是偏序關系≤，3≤6的含義是3整除6。大于或等于關系也是偏序關系，針對這個關系5≤4是指在大于或等于關系中5排在4的前面，也就是說5比4大。
在實際應用中，經常遇到的偏序關系是定義在一個記錄類型的數(shù)據(jù)集合上的。在該記錄類型中有一個主鍵域key，key域的類型是某一個偏序集，記錄的其他域稱為衛(wèi)星數(shù)據(jù)。比較線性表中的兩個元素li和lj的大小，實際上是比較li.key和lj.key的大小（這種比較當然也是偏序集中的比較）。舉例而言，某公司的數(shù)據(jù)庫里記 錄了員工的數(shù)據(jù)，每一項紀錄包括姓名，編號，年齡，工資等幾個域，如果以編號為key域對員工記錄排序，則是將員工記錄按照編號排序；如果以工資為key域對員工記錄排序，則是將員工記錄按照工資高低排序；如果以姓名為key域對員工記錄排序，則是以員工姓名的漢語拼音按照字典順序排序。
關于偏序集的具體概念和應用，請參見離散數(shù)學的相關資料。
如果一個排序算法利用輸入的線性表在原地重排其中元素，而沒有額外的內存開銷，這種排序算法叫做原地置換排序算法(in place sort)；如果排序后并不改變表中相同的元素原來的相對位置，那么這種排序算法叫做穩(wěn)定排序算法(stable sort)。
排序問題一般分為內排序( internal sorting )和外排序( external sorting )兩類：
1. 內排序：待排序的表中記錄個數(shù)較少，整個排序過程中所有的記錄都可以保留在內存中；
2. 外排序：待排序的記錄個數(shù)足夠多，以至于他們必須存儲在磁帶、磁盤上組成外部文件，排序過程中需要多次訪問外存。
內排序
待排序的表中記錄個數(shù)較少，整個排序過程中所有的記錄都可以保留在內存中，這樣的排序叫做內排序。
請參閱：
排序問題的計算復雜性
比較排序算法
冒泡排序
選擇排序
插入排序
快速排序
合并排序
shell排序
堆排序
線性時間排序算法
計數(shù)排序
基數(shù)排序
桶排序
冒泡排序 bubble sort
最簡單的排序方法是冒泡排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后，“次輕”的元素就浮到了次高位置。在作第二遍處理時，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。這個算法可實現(xiàn)如下。
procedure bubble_sort(var l:list);
var
i,j:position;
begin
1 for i:=first(l) to last(l)-1 do
2 for j:=first(l) to last(l)-i do
3 if l[j]>l[j+1] then
4 swap(l[j],l[j+1]); //交換l[j]和l[j+1]
end;
上述算法將較大的元素看作較重的氣泡，每次最大的元素沉到表尾。其中first(l)和last(l)分別表示線性表l的第一個元素和最后一個元素的位置，swap(x,y)交換變量x,y的值。上述算法簡單地將線性表的位置當作整數(shù)用for循環(huán)來處理，但實際上線性表可能用鏈表實現(xiàn)；而且上述算法將線性表元素的值當作其鍵值進行處理。不過這些并不影響表達該算法的基本思想。今后如果不加說明，所有的算法都用這種簡化方式表達。
容易看出該算法總共進行了n(n-1)/2次比較。如果swap過程消耗的時間不多的話，主要時間消耗在比較上，因而時間復雜性為o(n2)。但是如果元素類型是一個很大的紀錄，則swap過程要消耗大量的時間，因此有必要分析swap執(zhí)行的次數(shù)。
顯然算法bubble_sort在最壞情況下調用n(n-1)/2次swap過程。我們假設輸入序列的分布是等可能的。考慮互逆的兩個輸入序列l(wèi)1=k1,k2,..,kn和l2=kn,kn-1,..,k1。我們知道，如果ki>kj，且ki在表中排在kj前面，則在冒泡法排序時必定要將kj換到ki前面，即kj向前浮的過程中一定要穿過一次ki，這個過程要調用一次swap。對于任意的兩個元素ki和kj，不妨設ki>kj，或者在l1中ki排在kj前面，或者l2在中ki排在kj前面，兩者必居其一。因此對于任意的兩個元素ki和kj，在對l1和l2排序時，總共需要將這兩個元素對調一次。n個元素中任取兩個元素有cn2 種取法，因此對于兩個互逆序列進行排序，總共要調用cn2 =n(n-1)/2次swap，平均每個序列要調用n(n-1)/4次swap。那么算法bubble_sort調用swap的平均次數(shù)為n(n-1)/4。
可以對冒泡算法作一些改進，如果算法第二行的某次內循環(huán)沒有進行元素交換，則說明排序工作已經完成，可以退出外循環(huán)。可以用一個布爾變量來記錄內循環(huán)是否進行了記錄交換，如果沒有則終止外循環(huán)。
冒泡法的另一個改進版本是雙向掃描冒泡法（bi-directional bubble sort）。設被排序的表中各元素鍵值序列為：
483 67 888 50 255 406 134 592 657 745 683
對該序列進行3次掃描后會發(fā)現(xiàn)，第3此掃描中最后一次交換的一對紀錄是l[4]和l[5]：
50 67 255 134 | 406 483 592 657 683 745 888
顯然，第3次掃描(i=3)結束后l[5]以后的序列都已經排好序了，所以下一次掃描不必到達last(l)-i=11-4=7，即第2行的for 循環(huán)j不必到達7，只要到達4-1=3就可以了。按照這種思路，可以來回地進行掃描，即先從頭掃到尾，再從尾掃到頭。這樣就得到雙向冒泡排序算法：
procedure bi-directional_bubble_sort(var l:list);
var
low,up,t,i:position;
begin
1 low:=first(l);up:=last(l);
2 while up>low do
begin
3 t:=low;
4 for i:=low to up-1 do
5 if l[i]>l[i+1] then
begin
6 swap(l[i],l[i+1]);
7 t:=i;
end;
8 up:=t;
9 for i:=up downto low+1 do
10 if l[i]< l[i-1] then
begin
11 swap(l[i],l[i-1]);
12 t:=i;
end;
13 low:=t;
end;
end;
算法利用兩個變量low和up記錄排序的區(qū)域l[low..up]，用變量t 記錄最近一次交換紀錄的位置，4-7行從前向后掃描，9-12行從后向前掃描，每次掃描以后利用t所記錄的最后一次交換記錄的位置，并不斷地縮小需要排序的區(qū)間，直到該區(qū)間只剩下一個元素。
直觀上來看，雙向冒泡法先讓重的氣泡沉到底下，然后讓輕的氣泡浮上來，然后再讓較大氣泡沉下去，讓較輕氣泡浮上來，依次反復，直到排序結束。
雙向冒泡排序法的性能分析比較復雜，目前暫缺，那位朋友知道請告訴我。
冒泡排序法和雙向冒泡排序法是原地置換排序法，也是穩(wěn)定排序法，如果算法bubble_sort中第3行的比較條件l[j]>l[j+1]改為l[j]>= l[j+1]，則不再是穩(wěn)定排序法。
選擇排序 selection sort
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將l[i..n]中最小者與l[i]交換位置。這樣，經過i遍處理之后，前i個記錄的位置已經是正確的了。
選擇排序算法可實現(xiàn)如下。
procedure selection_sort(var l:list);
var
i,j,s:position;
begin
1 for i:=first(l) to last(l)-1 do
begin
2 s:=i;
3 for j:=i+1 to last(l) do
4 if l[j]< l[s] then
5 s:=j; //記錄l[i..n]中最小元素的位置
6 swap(l[i],l[s]); //交換l[i],l[s]
end;
end;
算法selection_sort中里面的一個for循環(huán)需要進行n-i次比較，所以整個算法需要
次比較。
顯而易見，算法selection_sort中共調用了n-1次swap過程。選擇排序法是一個原地置換排序法，也是穩(wěn)定排序法。
插入排序 insertion sort
插入排序的基本思想是，經過i-1遍處理后,l[1..i-1]己排好序。第i遍處理僅將l[i]插入l[1..i-1]的適當位置，使得l[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較l[i]和l[i-1]，如果l[i-1]≤ l[i]，則l[1..i]已排好序，第i遍處理就結束了；否則交換l[i]與l[i-1]的位置，繼續(xù)比較l[i-1]和l[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得l[j] ≤l[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
圖1 對4個元素進行插入排序
在下面的插入排序算法中，為了寫程序方便我們可以引入一個哨兵元素l[0]，它小于l[1..n]中任一記錄。所以，我們設元素的類型elementtype中有一個常量-∞，它比可能出現(xiàn)的任何記錄都小。如果常量-∞不好事先確定，就必須在決定l[i]是否向前移動之前檢查當前位置是否為1，若當前位置已經為1時就應結束第i遍的處理。另一個辦法是在第i遍處理開始時，就將l[i]放入l[0]中，這樣也可以保證在適當?shù)臅r候結束第i遍處理。下面的算法中將對當前位置進行判斷。
插入排序算法如下：
procedure selection_sort(var l:list);
var
i,j:position;
v:elementtype;
begin
1 for i:=first(l)+1 to last(l) do
begin
2 v:=l[i];
3 j:=i;
4 while (j<>first(l))and(l[j-1]< v) do //循環(huán)找到插入點
begin
5 l[j]:=l[j-1]; //移動元素
6 j:=j-1;
end;
7 l[j]:=v; //插入元素
end;
end;
下面考慮算法insertion_sort的復雜性。對于確定的i，內while循環(huán)的次數(shù)為o(i)，所以整個循環(huán)體內執(zhí)行了∑o(i)=o(∑i)，其中i從2到n。即比較次數(shù)為o(n2)。如果輸入序列是從大到小排列的，那么內while循環(huán)次數(shù)為i-1次，所以整個循環(huán)體執(zhí)行了∑(i-1)=n(n-1)/2次。由此可知，最壞情況下，insertion_sort要比較ω(n2)次。
如果元素類型是一個很大的紀錄，則算法第5行要消耗大量的時間，因此有必要分析移動元素的次數(shù)。經過分析可知，平均情況下第5行要執(zhí)行n(n-1)/4次，分析方法與冒泡排序的分析相同。
如果移動元素要消耗大量的時間，則可以用鏈表來實現(xiàn)線性表，這樣insertion_sort可以改寫如下(當然前一個算法同樣也適用于鏈表，只不過沒下面這個好，但是下面算法這個比較復雜)：
注意：在下面的算法中鏈表l增加了一個哨兵單元，其中的元素為-∞，即線性表l的第一個元素是l^.next^
procedure selection_sort_ii(var l:plist);
var
i,j,tmp:position;
begin
1 if l^.next=nil then exit; //如果鏈表l為空則直接退出
2 i:=l^.next; //i指向l的第一個元素，注意，l有一個哨兵元素，因此l^.next^才是l的第一個元素
3 while i^.next<>nil do
begin
4 tmp:=i^.next; //tmp指向l[i]的下一個位置
5 j:=l;
6 while (j<>i)and(tmp^.data>=j^.next^.data) do //從前向后找到tmp的位置，tmp應該插在j后面
7 j:=j^.next;
8 if j<>i then //j=i說明不需要改變tmp的位置
begin
9 i^.next:=tmp^.next; //將tmp從i后面摘除
10 tmp^.next:=j^.next; //在j后面插入tmp
11 j^.next:=tmp;
end
12 else i:=i^.next; //否則i指向下一個元素
end;
end;
上述改進算法主要是利用鏈表刪除和插入元素方便的特性，對于數(shù)組則不適用。
插入排序法是一個原地置換排序法，也是一個穩(wěn)定排序法。插入法雖然在最壞情況下復雜性為θ(n2)，但是對于小規(guī)模輸入來說，插入排序法是一個快速的原地置換排序法。許多復雜的排序法，在規(guī)模較小的情況下，都使用插入排序法來進行排序，比如快速排序和桶排序。
下面是一個java applet制作的插入排序演示程序。
快速排序 quick sort
我們已經知道，在決策樹計算模型下，任何一個基于比較來確定兩個元素相對位置的排序算法需要ω(nlogn)計算時間。如果我們能設計一個需要o(n1ogn)時間的排序算法，則在漸近的意義上，這個排序算法就是最優(yōu)的。許多排序算法都是追求這個目標。
下面介紹快速排序算法，它在平均情況下需要o(nlogn)時間。這個算法是由c.a.r.hoare發(fā)明的。
算法的基本思想
快速排序的基本思想是基于分治策略的。對于輸入的子序列l(wèi)[p..r]，如果規(guī)模足夠小則直接進行排序，否則分三步處理：
分解(divide)：將輸入的序列l(wèi)[p..r]劃分成兩個非空子序列l(wèi)[p..q]和l[q+1..r]，使l[p..q]中任一元素的值不大于l[q+1..r]中任一元素的值。
遞歸求解(conquer)：通過遞歸調用快速排序算法分別對l[p..q]和l[q+1..r]進行排序。
合并(merge)：由于對分解出的兩個子序列的排序是就地進行的，所以在l[p..q]和l[q+1..r]都排好序后不需要執(zhí)行任何計算l[p..r]就已排好序。
這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經典應用實例之一。
算法的實現(xiàn)
算法quick_sort的實現(xiàn)：
注意：下面的記號l[p..r]代表線性表l從位置p到位置r的元素的集合，但是l并不一定要用數(shù)組來實現(xiàn)，可以是用任何一種實現(xiàn)方法（比如說鏈表），這里l[p..r]只是一種記號。
procedure quick_sort(p,r:position;var l:list);
const
e=12;
var
q:position;
begin
1 if r-p<=e then insertion_sort(l,p,r)//若l[p..r]足夠小則直接對l[p..r]進行插入排序
else begin
2 q:=partition(p,r,l);//將l[p..r]分解為l[p..q]和l[q+1..r]兩部分
3 quick_sort(p,q,l); //遞歸排序l[p..q]
4 quick_sort(q+1,r,l);//遞歸排序l[q+1..r]
end;
end;
對線性表l[1..n]進行排序，只要調用quick_sort(1,n,l)就可以了。算法首先判斷l(xiāng)[p..r]是否足夠小，若足夠小則直接對l[p..r]進行排序，sort可以是任何一種簡單的排序法，一般用插入排序。這是因為，對于較小的表，快速排序中劃分和遞歸的開銷使得該算法的效率還不如其它的直接排序法好。至于規(guī)模多小才算足夠小，并沒有一定的標準，因為這跟生成的代碼和執(zhí)行代碼的計算機有關，可以采取試驗的方法確定這個規(guī)模閾值。經驗表明，在大多數(shù)計算機上，取這個閾值為12較好，也就是說，當r-p<=e=12即l[p..r]的規(guī)模不大于12時，直接采用插入排序法對l[p..r]進行排序(參見 sorting and searching algorithms: a cookbook)。當然，比較方便的方法是取該閾值為1，當待排序的表只有一個元素時，根本不用排序(其實還剩兩個元素時就已經在partition函數(shù)中排好序了)，只要把第1行的if語句該為if p=r then exit else ...。這就是通常教科書上看到的快速排序的形式。
注意：算法quick_sort中變量q的值一定不能等于r，否則該過程會無限遞歸下去，永遠不能結束。因此下文中在partition函數(shù)里加了限制條件，避免q=r情況的出現(xiàn)。
算法quick_sort中調用了一個函數(shù)partition，該函數(shù)主要實現(xiàn)以下兩個功能：
1. 在l[p..r]中選擇一個支點元素pivot;
2. 對l[p..r]中的元素進行整理，使得l[p..q]分為兩部分l[p..q]和l[q+1..r]，并且l[p..q]中的每一個元素的值不大于pivot，l[q+1..r]中的每一個元素的值不小于pivot，但是l[p..q]和l[q+1..r]中的元素并不要求排好序。
快速排序法改進性能的關鍵就在于上述的第二個功能，因為該功能并不要求l[p..q]和l[q+1..r]中的元素排好序。
函數(shù)partition可以實現(xiàn)如下。以下的實現(xiàn)方法是原地置換的，當然也有不是原地置換的方法，實現(xiàn)起來較為簡單，這里就不介紹了。
function partition(p,r:position;var l:list):position;
var
pivot:elementtype;
i,j:position;
begin
1 pivot:=select_pivot(p,r,l); //在l[p..r]中選擇一個支點元素pivot
2 i:=p-1;
3 j:=r+1;
4 while true do
begin
5 repeat j:=j-1 until l[j]<=pivot; //移動左指針，注意這里不能用while循環(huán)
6 repeat i:=i+1 until l[i]>=pivot; //移動右指針，注意這里不能用while循環(huán)
7 if i< j then swap(l[i],l[j]) //交換l[i]和l[j]
8 else if j<>r then return j //返回j的值作為分割點
9 else return j-1; //返回j前一個位置作為分割點
end;
end;
該算法的實現(xiàn)很精巧。其中，有一些細節(jié)需要注意。例如，算法中的位置i和j不會超出a[p..r]的位置界，并且該算法的循環(huán)不會出現(xiàn)死循環(huán)，如果將兩個repeat語句換為while則要注意當l[i]=l[j]=pivot且i<j時i和j的值都不再變化，會出現(xiàn)死循環(huán)。
另外，最后一個if..then..語句很重要，因為如果pivot取的不好，使得partition結束時j正好等于r，則如前所述，算法quick_sort會無限遞歸下去；因此必須判斷j是否等于r，若j=r則返回j的前驅。
以上算法的一個執(zhí)行實例如圖1所示，其中pivot=l[p]=5：
圖1 partition過程的一個執(zhí)行實例
partition對l[p..r]進行劃分時，以pivot作為劃分的基準，然后分別從左、右兩端開始，擴展兩個區(qū)域l[p..i]和l[j..r]，使得l[p..i]中元素的值小于或等于pivot，而l[j..r]中元素的值大于或等于pivot。初始時i=p-1，且j=i+1，從而這兩個區(qū)域是空的。在while循環(huán)體中，位置j逐漸減小，i逐漸增大，直到l[i]≥pivot≥l[j]。如果這兩個不等式是嚴格的，則l[i]不會是左邊區(qū)域的元素，而l[j]不會是右邊區(qū)域的元素。此時若i在j之前，就應該交換l[i]與l[j]的位置，擴展左右兩個區(qū)域。 while循環(huán)重復至i不再j之前時結束。這時l[p..r]己被劃分成l[p..q]和l[q+1..r]，且滿足l[p..q]中元素的值不大于l[q+1..r]中元素的值。在過程partition結束時返回劃分點q。
尋找支點元素select_pivot有多種實現(xiàn)方法，不同的實現(xiàn)方法會導致快速排序的不同性能。根據(jù)分治法平衡子問題的思想，我們希望支點元素可以使l[p..r]盡量平均地分為兩部分，但實際上這是很難做到的。下面我們給出幾種尋找pivot的方法。
1. 選擇l[p..r]的第一個元素l[p]的值作為pivot；
2. 選擇l[p..r]的最后一個元素l[r]的值作為pivot；
3. 選擇l[p..r]中間位置的元素l[m]的值作為pivot；
4. 選擇l[p..r]的某一個隨機位置上的值l[random(r-p)+p]的值作為pivot；
按照第4種方法隨機選擇pivot的快速排序法又稱為隨機化版本的快速排序法，在下面的復雜性分析中我們將看到該方法具有平均情況下最好的性能，在實際應用中該方法的性能也是最好的。
下面是一個快速排序的java applet演示程序，該程序使用第一種pivot選擇法，即選l[p]為pivot，因此partition過程作了一些簡化，與我們這里的partition過程實現(xiàn)方法不同，但功能相同。該程序是針對用數(shù)組實現(xiàn)的線性表，用c語言實現(xiàn)的。
線性時間排序算法
我們已經知道，通過比較確定兩個元素之間相對位置的比較排序算法計算時間復雜性下界為o(nlogn)，要想改進這個下界，就必須對輸入的數(shù)據(jù)作某些限制。下面介紹的幾種排序算法都可以在o(n)時間內對一個線性表進行排序，但是他們要求輸入數(shù)據(jù)滿足某種條件。
計數(shù)排序
基數(shù)排序
桶排序
計數(shù)排序 counting sort
計數(shù)排序是一個非基于比較的線性時間排序算法。它對輸入的數(shù)據(jù)有附加的限制條件：
1. 輸入的線性表的元素屬于有限偏序集s；
2. 設輸入的線性表的長度為n，|s|=k（表示集合s中元素的總數(shù)目為k），則k=o(n)。
在這兩個條件下，計數(shù)排序的復雜性為o(n)。
計數(shù)排序算法的基本思想是對于給定的輸入序列中的每一個元素x，確定該序列中值小于x的元素的個數(shù)。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小于x的值，則x可以直接存放在輸出序列的第18個位置上。當然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上，因此，上述方案還要作適當?shù)男薷摹?br>
假設輸入的線性表l的長度為n，l=l1,l2,..,ln；線性表的元素屬于有限偏序集s，|s|=k且k=o(n)，s={s1,s2,..sk}；則計數(shù)排序算法可以描述如下：
1. 掃描整個集合s，對每一個si∈s，找到在線性表l中小于等于si的元素的個數(shù)t(si)；
2. 掃描整個線性表l，對l中的每一個元素li，將li放在輸出線性表的第t(li)個位置上，并將t(li)減1。
具體的實現(xiàn)如下。
注意：在以下的討論中，為了方便，我們假設線性表是用數(shù)組來實現(xiàn)的，并且假設線性表的元素類型telement為整型，其值在1..k之間，線性表的長度為n，且k=o(n)。這些假設對計數(shù)排序算法沒有實質的影響，但是可以使以下介紹的算法看起來容易理解。
在下面的計數(shù)排序算法中，我們假設l為輸入的長度為n的線性表，輸出的排序結果存放在線性表r中。算法中還用到一個輔助表tmp用于對輸入元素進行計數(shù)。
type
telement=1..k;
tlist=array [1..maxlength] of telement;
tposition=integer;
procedure counting_sort(var l,r:tlist);
var
i,j:integer;
tmp:tlist;
begin
1 for i:=1 to k do tmp[i]:=0;
2 for j:=1 to n do inc(tmp[l[j]]);
//執(zhí)行完上面的循環(huán)后，tmp[i]的值是l中等于i的元素的個數(shù)
3 for i:=2 to k do tmp[i]:=tmp[i]+tmp[i-1];
//執(zhí)行完上面的循環(huán)后，tmp[i]的值是l中小于等于i的元素的個數(shù)
4 for j:=n downto 1 do //注意這里的downto保證了排序的穩(wěn)定性
begin
5 r[tmp[l[j]]]:=l[j];//l[j]存放在輸出數(shù)組r的第tmp[l[j]]個位置上
6 dec(tmp[l[j]]); //tmp[l[j]]表示l中剩余的元素中小于等于l[j]的元素的個數(shù)
end;
end;
圖1所示的是counting_sort作用于一個輸入數(shù)組l[1..8]上的過程，其中l(wèi)的每一個元素都是不大于k=6的正整數(shù)。
圖1 計數(shù)排序算法演示
容易理解，算法的第(l)行是對數(shù)組tmp初始化。第(2)行檢查每個輸入元素。如果輸入元素的鍵值為i，則tmp[i]增1。因此，在第(2)行執(zhí)行結束后，tmp[i]中存放著值等于i的輸入元素個數(shù)，i=1,2,..,k。算法的第(3)行，對每個i=1,2,..,i，統(tǒng)計值小于或等于i的輸入元素個數(shù)。最后在(4)-(8)行中，將每個元素l[j]存放到輸出數(shù)組r中相應的最終位置上。如果所有n個元素的值都不相同，則共有tmp[l[j]]個元素的鍵值小于或等于l[j]，而小于l[j]的元素有tmp[l[j]]-1個，因此tmp[l[j]]就是l[j]在輸出數(shù)組r中的正確位置。當輸入元素有相同的值時，每將一個l[j]存放到數(shù)組r時，tmp[l[j]]就減1，使下
個值等于l[j]的元素存放在輸出數(shù)組r中存放元素l[j]的前一個位置上。
計數(shù)排序算法的計算時間復雜性很容易分析。其中，第(1)行需要o(k)時間；第(2)行需要o(n)時間，第(3)行需要o(k)時間；第(4)-(8)行的for循環(huán)需要o(n)時間。這樣，整個算法所需的計算間為o(n+k)。當k=o(n)時，算法的計算時間復雜性為o(n)。
我們看到，計數(shù)排序算法沒有用到元素間的比較，它利用元素的實際值來確定它們在輸出數(shù)組中的位置。因此，計數(shù)排序算法不是一個基于比較的排序算法，從而它的計算時間下界不再是ω(nlogn)。另一方面，計數(shù)排序算法之所以能取得線性計算時間的上界是因為對元素的取值范圍作了一定限制，即k=o(n)。如果k=n2,n3,..，就得不到線性時間的上界。此外，我們還看到，由于算法第4行使用了downto語句，經計數(shù)排序，輸出序列中值相同的元素之間的相對次序與他們在輸入序列中的相對次序相同，換句話說，計數(shù)排序算法是一個穩(wěn)定的排序算法，但顯然不是原地置換排序算法。
基數(shù)排序 radix sort
基數(shù)排序是一種用在老式穿卡機上的算法。一張卡片有80列，每列可在12個位置中的任一處穿孔。排序器可被機械地"程序化"以檢查每一迭卡片中的某一列，再根據(jù)穿孔的位置將它們分放12個盒子里。這樣，操作員就可逐個地把它們收集起來。其中第一個位置穿孔的放在最上面，第二個位置穿孔的其次，等等。
對十進制數(shù)字來說，每列中只用到10個位置(另兩個位置用于編碼非數(shù)值字符)。一個d位數(shù)占用d個列。因為卡片排序器一次只能查看一個列，要對n張片上的d位數(shù)進行排序就要有個排序算法。
直感上，大家可能覺得應該按最重要的一位排序，然后對每個盒子中的數(shù)遞歸地排序，最后把結果合并起來。不幸的是，為排序每一個盒子中的數(shù)，10個盒子中的9個必須先放在一邊，這個過程產生了許多要加以記錄的中間卡片堆。
與人們的直感相反，基數(shù)排序是首先按最不重要的一位數(shù)字排序來解決卡片排序問題的。同樣，把各堆卡片收集成一迭，其中0號盒子中的在1號盒子中的前面，后者又在2號盒子中的前面，等等。然后對整個一迭卡片按次重要位排序，并把結果同樣地合并起來。重復這個過程，直到對所有的d位數(shù)字都進行了排序。所以，僅需要n遍就可將一迭卡片排好序。圖1說明了基數(shù)排序作“一迭”7個三位數(shù)的過程。第一列為輸入，其余各列示出了對各個數(shù)位進行逐次排序后表的情形。垂直向上的箭頭指示了當前要被加以排序的數(shù)位。
圖1 基數(shù)排序作用于一個由7個3位數(shù)組成的表上的過程
關于這個算法很重要的一點就是按位排序要穩(wěn)定。由卡片排序器所故的排序是穩(wěn)定的，但操作員在把卡片從盒子里拿出來時不能改變他們的次序，即使某一盒子中所有卡片在給定列上的穿孔位置都相同。
在一臺典型的順序隨機存取計算機上，有時采用基數(shù)排序來對有多重域關鍵字的記錄進行排序。例如，假設我們想根據(jù)三個關鍵字處、月和日來對日期排序。對這個問題，可以用帶有比較函數(shù)的排序算法來做。給定兩個日期，先比較年份，如果相同，再比較月份，如果再相同，再比較日。這兒我們可以采用另一個方法，即用一種穩(wěn)定的排序方法對所給信息進行三次排序：先對日，其次對月，再對年。
基數(shù)排序的代碼是很簡單的、下面的過程假設長度為n的數(shù)組a中的每個元素都有d位數(shù)字，其中第1位是最低的，第d位是最高位。
procedure radix_sort(var l:list;d:integer);
var
i:integer;
begin
1 for i:=1 to d do
2 使用一種穩(wěn)定的排序方法來對數(shù)組l按數(shù)字i進行排序;
end;
基數(shù)排序的正確性可以通過對正在被排序的列進行歸納而加以證明。對本算法時間代價的分析要取決于選擇哪種穩(wěn)定的中間排序算法。當每位數(shù)字都界于l到k之間，且k不太大時，可以選擇計數(shù)排序。對n個d位數(shù)的每一遍處理的時間為o(n+k)，共有d遍，故基數(shù)排序的總時間為θ(dn+kd)。當d為常數(shù)，k=o(n)時，基數(shù)排序有線性運行時間。
某些計算機科學家傾向于把一個計算機字中所含位數(shù)看成是θ(lgn)。具體一點說，假設共有dlgn位數(shù)字，d為正常數(shù)。這樣，如果待排序的每個數(shù)恰能容于一個計算機字內，我們就可以把它視為一個以n為基數(shù)的d位數(shù)。看一個例子：對一百萬個64位數(shù)排序。通過把這些數(shù)當作是以216為基數(shù)的四位數(shù)，用基數(shù)排序四遍就可完成排序。這與一個典型的o(nlgn)比較排序相比要好得多，后者對每一個參加排序的數(shù)約要lgn=20次操作。但有一點不理想，即采用計數(shù)排序作為中間穩(wěn)定排序算法的基數(shù)排序版本不能夠進行原地置換排序，而很多o(nlgn)比較排序算法卻是可以的。因此，當內存比較緊張時，一般來說選擇快速排序更合適些。
桶排序 bin sort
平均情況下桶排序以線性時間運行。像計數(shù)排序一樣，桶排序也對輸入作了某種假設， 因而運行得很快。具體來說，計數(shù)排序假設輸入是由一個小范圍內的整數(shù)構成，而桶排序則 假設輸入由一個隨機過程產生，該過程將元素一致地分布在區(qū)間[0，1)上。
桶排序的思想就是把區(qū)間[0，1)劃分成n個相同大小的子區(qū)間，或稱桶，然后將n個輸入數(shù)分布到各個桶中去。因為輸入數(shù)均勻分布在[0，1)上，所以一般不會有很多數(shù)落在 一個桶中的情況。為得到結果，先對各個桶中的數(shù)進行排序，然后按次序把各桶中的元素列 出來即可。
在桶排序算法的代碼中，假設輸入是個含n個元素的數(shù)組a，且每個元素滿足0≤ a[i]<1。另外還需要一個輔助數(shù)組b[o..n-1]來存放鏈表實現(xiàn)的桶，并假設可以用某種機制來維護這些表。
桶排序的算法如下，其中floor(x)是地板函數(shù)，表示不超過x的最大整數(shù)。
procedure bin_sort(var a:list);
begin
1 n:=length(a);
2 for i:=1 to n do
3 將a[i]插到表b[floor(n*a[i])]中;
4 for i:=0 to n-1 do
5 用插入排序對表b[i]進行排序;
6 將表b[0],b[1],...,b[n-1]按順序合并;
end;
圖1 bin_sort的操作
圖1演示了桶排序作用于有10個數(shù)的輸入數(shù)組上的操作過程。(a)輸入數(shù)組a[1..10]。(b)在該算法的第5行后的有序表(桶)數(shù)組b[0..9]。桶i中存放了區(qū)間[i/10，(i+1)/10]上的值。排序輸出由表b[o]、b[1]、...、b[9]的按序并置構成。
要說明這個算法能證確地工作，看兩個元素a[i]和a[j]。如果它們落在同一個桶中，則它們在輸出序列中有著正確的相對次序，因為它們所在的桶是采用插入排序的。現(xiàn)假設它們落到不同的桶中，設分別為b[i']和b[j']。不失一般性，假設i'<j'。在算法的代碼中，當?shù)?行中將b中的表并置起來時，桶b[i']中的元素先于桶b[j']中的元素，因而在輸出序列中a[i]先于a[j]。現(xiàn)在要證鰽[i]≤a[j]。假設情況正好相反，我們有：
i'=floor(n*a[i])≥floor(n*a[j])=j'
得矛盾 (因為i'<j')，從而證明桶排序能正確地工作。
現(xiàn)在來分析算法的運行時間。除第5行外，所有各行在最壞情況的時間都是o(n)。第5行中檢查所有桶的時間是o(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的時間。
為分析插人排序的時間代價，設ni為表示桶b[i]中元素個數(shù)的隨機變量。因為插入排序以二次時間運行，故為排序桶b[i]中元素的期望時間為e[o(ni2)]=o(e[ni2])，對各個桶中的所有元素排序的總期望時間為：
(1)
為了求這個和式，要確定每個隨機變量ni的分布。我們共有n個元素，n個桶。某個元素落到桶b[i]的概率為l/n，因為每個桶對應于區(qū)間[0，1)的l/n。這種情況與投球的例子很類似：有n個球 (元素)和n個盒子 (桶)，每次投球都是獨立的，且以概率p=1/n落到任一桶中。這樣，ni=k的概率就服從二項分布b(k;n,p)，其期望值為e[ni]=np=1，方差v[ni]=np(1-p)=1-1/n。對任意隨機變量x，有:
(2)
將這個界用到(1)式上，得出桶排序中的插人排序的期望運行時間為o(n)。因而，整個桶排序的期望運行時間就是線性的。
下面的java applet程序演示了桶排序的基本思想。
在該演示程序中，線性表的元素類型為整型，桶的標號為整數(shù)，算法將值為i的元素放入標號為i的桶中，再按照桶的標號的順序將元素依次取出，就得到了最終的排序結果。
