560
排序算法(1)
算法是程序設計的精髓，程序設計的實質就是構造解決問題的算法，將其解釋為計算機語言。在這裏您可以了解到：
算法定義
偽代碼的使用
算法的複雜性
算法設計策略
常用算法
這裏所有的算法都以一種類似Pascal語言的偽代碼描述，請參閱偽代碼的使用。
新增內容
關於數論的算法——數論基本知識（May 6, 2001）
動態規劃重新整理 （January 15, 2001）
圖的深度優先遍曆 （January 21, 2001）
圖的廣度優先遍曆 （January 21, 2001）
圖的拓撲排序 （January 21, 2001）
算法 Algorithm
算法是在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗點說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現的算法，後者是操作實現的算法。
一個算法應該具有以下五個重要的特征：
1. 有窮性： 一個算法必須保證執行有限步之後結束；
2. 確切性： 算法的每一步驟必須有確切的定義；
3. 輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件；
4. 輸出：一個算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的算法是毫無意義的；
5. 可行性： 算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算後即可完成。
Did you know
Algorithm 一詞的由來
Algorithm (算法)一詞本身就十分有趣。初看起來，這個詞好像是某人打算要寫“Logarithm”(對數)一詞但卻把頭四個字母寫的前後顛倒了。這個詞一直到 1957年之前在Webster's New World Dictionary(《韋氏新世界詞典》)中還未出現，我們隻能找到帶有它的古代涵義的較老形式的“Algorism”(算術)，指的是用阿拉伯數字進 行算術運算的過程。在中世紀時，珠算家用算盤進行計算，而算術家用算術進行計算。中世紀之後，對這個詞的起源已經拿不準了，早期的語言學家試圖推斷它的來 曆，認為它是從把algiros(費力的)+arithmos(數字)組合起來派生而成的，但另一些人則不同意這種說法，認為這個詞是從“喀斯迪爾國王 Algor”派生而來的。最後，數學史學家發現了algorism(算術)一詞的真實起源：它來源於著名的Persian Textbook(《波斯教科書》)的作者的名字Abu Ja'far Mohammed ibn Mûsâ al-Khowârizm （約公元前825年）——從字麵上看，這個名字的意思是“Ja'far 的父親，Mohammed 和 Mûsâ 的兒子，Khowârizm 的本地人”。Khowârizm 是前蘇聯XИBA(基發) 的小城鎮 。Al-Khowârizm 寫了著名的書Kitab al jabr w'al-muqabala (《複原和化簡的規則》)；另一個詞，“algebra”(代數)，是從他的書的標題引出來的，盡管這本書實際上根本不是講代數的。
逐漸 地，“algorism”的形式和意義就變得麵目全非了。如牛津英語字典所說明的，這個詞是由於同arithmetic(算術)相混淆而形成的錯拚詞。由 algorism又變成algorithm。一本早期的德文數學詞典 Vollstandiges Mathematisches Lexicon (《數學大全辭典》) ，給出了Algorithmus (算法)一詞的如下定義：“在這個名稱之下，組合了四種類型的算術計算的概念，即加法、乘法、減法、除法”。拉頂短語algorithmus infinitesimalis (無限小方法) ，在當時就用來表示Leibnitz(萊布尼茲)所發明的以無限小量進行計算的微積分方法。
1950 年左右，algorithm一詞經常地同歐幾裏德算法(Euclid's algorithm)聯係在一起。這個算法就是在歐幾裏德的《幾何原本》(Euclid's Elements ,第VII卷，命題i和ii)中所闡述的求兩個數的最大公約數的過程(即輾轉相除法)。
左上方的圖片是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稱為偏序集。
注意，這裏的≤不是指數的大小，而是指在偏序關係中的順序性。x≤y的含義是：按照這個序，x排 在y前麵。根據不同的偏序定義，≤有不同的解釋。例如整除關係是偏序關係≤，3≤6的含義是3整除6。大於或等於關係也是偏序關係，針對這個關係5≤4是 指在大於或等於關係中5排在4的前麵，也就是說5比4大。
在實際應用中，經常遇到的偏序關係是定義在一個記錄類型的數據集合上的。在該記 錄類型中有一個主鍵域key，key域的類型是某一個偏序集，記錄的其他域稱為衛星數據。比較線性表中的兩個元素Li和Lj的大小，實際上是比較 Li.key和Lj.key的大小（這種比較當然也是偏序集中的比較）。舉例而言，某公司的數據庫裏記 錄了員工的數據，每一項紀錄包括姓名，編號，年齡，工資等幾個域，如果以編號為key域對員工記錄排序，則是將員工記錄按照編號排序；如果以工資為key 域對員工記錄排序，則是將員工記錄按照工資高低排序；如果以姓名為key域對員工記錄排序，則是以員工姓名的漢語拚音按照字典順序排序。
關於偏序集的具體概念和應用，請參見離散數學的相關資料。
如果一個排序算法利用輸入的線性表在原地重排其中元素，而沒有額外的內存開銷，這種排序算法叫做原地置換排序算法(in place sort)；如果排序後並不改變表中相同的元素原來的相對位置，那麼這種排序算法叫做穩定排序算法(stable sort)。
排序問題一般分為內排序( internal sorting )和外排序( external sorting )兩類：
1. 內排序：待排序的表中記錄個數較少，整個排序過程中所有的記錄都可以保留在內存中；
2. 外排序：待排序的記錄個數足夠多，以至於他們必須存儲在磁帶、磁盤上組成外部文件，排序過程中需要多次訪問外存。
內排序
待排序的表中記錄個數較少，整個排序過程中所有的記錄都可以保留在內存中，這樣的排序叫做內排序。
請參閱：
排序問題的計算複雜性
比較排序算法
冒泡排序
選擇排序
插入排序
快速排序
合並排序
Shell排序
堆排序
線性時間排序算法
計數排序
基數排序
桶排序
冒泡排序 Bubble Sort
最 簡單的排序方法是冒泡排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們 要對這個“氣泡”序列處理若幹遍。所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不 對，即“輕”的元素在下麵，就交換它們的位置。顯然，處理一遍之後，“最輕”的元素就浮到了最高位置；處理二遍之後，“次輕”的元素就浮到了次高位置。在 作第二遍處理時，由於最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前麵i-1遍的處 理，它們已正確地排好序。這個算法可實現如下。
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的值。上述算法簡單地將線性表的位置當作整數用for循環來處理，但實際上線性表可能用鏈表實現；而且上述算法將線性表 元素的值當作其鍵值進行處理。不過這些並不影響表達該算法的基本思想。今後如果不加說明，所有的算法都用這種簡化方式表達。
容易看出該算法總共進行了n(n-1)/2次比較。如果swap過程消耗的時間不多的話，主要時間消耗在比較上，因而時間複雜性為O(n2)。但是如果元素類型是一個很大的紀錄，則Swap過程要消耗大量的時間，因此有必要分析swap執行的次數。
顯 然算法Bubble_Sort在最壞情況下調用n(n-1)/2次Swap過程。我們假設輸入序列的分布是等可能的。考慮互逆的兩個輸入序列L1=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的平均次數為n(n-1) /4。
可以對冒泡算法作一些改進，如果算法第二行的某次內循環沒有進行元素交換，則說明排序工作已經完成，可以退出外循環。可以用一個布爾變量來記錄內循環是否進行了記錄交換，如果沒有則終止外循環。
冒泡法的另一個改進版本是雙向掃描冒泡法（Bi-Directional Bubble Sort）。設被排序的表中各元素鍵值序列為：
483 67 888 50
最後更新：2017-04-02 00:06:15