排序這一研究領(lǐng)域在計算機科學(xué)中占有相當(dāng)重要的地位，不僅僅是因為它有著廣闊的應(yīng)用場前景啊犬，其本身也具有理論研究意義灼擂。
排序的基本概念
對于文件而言，排序就是根據(jù)記錄關(guān)鍵字值的遞增或者遞減關(guān)系將記錄的次序進行重新排序觉至，使得原來一組次序任意的記錄轉(zhuǎn)變?yōu)榘雌潢P(guān)鍵字值有序排列的一組記錄缤至。排序過程理解為一個按值無序的數(shù)據(jù)元素序列轉(zhuǎn)換為一個按值有序排序的數(shù)據(jù)元素序列的過程。從小到大稱為升序或者正序關(guān)系康谆；從大到小稱為逆序或者降序關(guān)系。排序又稱為分類嫉到。排序能夠作為提高查找時間效率的手段沃暗。
排序的分類
可以從不同觀點角度將排序操作分為不同的種類。
1.內(nèi)排序 和 外排序
根據(jù)排序過程中所使用的 內(nèi)何恶、外存儲器情況的不同孽锥，可以將排序分為 內(nèi)部排序 和 外部排序兩大類。簡稱 內(nèi)排序和外排序细层。
內(nèi)排序是指惜辑，當(dāng)參加排序的數(shù)量不大是，在排序過程中將全部信息存放在內(nèi)存中處理的排序方法疫赎。當(dāng)參加排序的數(shù)據(jù)量較大盛撑，以至于內(nèi)存不足以依次存放全部信息，在排序過程中需要通過內(nèi)存與外存之間的數(shù)據(jù)交換來達到排序目的捧搞，這種排序方式成為外排序抵卫。
外排序的速度要比內(nèi)排序的速度慢很多。
2.穩(wěn)定性排序 和 非穩(wěn)定性排序
通常把參加排序的項稱為排序碼或者排序項胎撇。對于具有同一排序碼的多個記錄而言介粘，若采用的排序方法使得排序后記錄的相對位置保持不變，則稱此排序為穩(wěn)定的晚树，否則為不穩(wěn)定的姻采，相應(yīng)的排序方法為穩(wěn)定性排序方法 和 非穩(wěn)定排序方法，這種特性是有用的爵憎。
3.連續(xù)順序文件排序 和 鏈表排序
根據(jù) 文件在存儲介質(zhì)上的組織方式劃分排序的種類慨亲，可以分為連續(xù)順序文件排序 和 鏈表排序。
連續(xù)順序文件排序：由于記錄之間的邏輯順序是通過物理地址的先后來映射纲堵，因而在排序過程中需要移動記錄的位置巡雨。
鏈表排序：文件中的一個記錄對應(yīng)著鏈表中的一個鏈結(jié)點，記錄之間的邏輯順序是通過指針來反映的席函，因而排序過程中不必移動記錄铐望，只需修改相應(yīng)指針的指向。
內(nèi)排序
內(nèi)排序方法的種類很多，如果按照完成排序所需的工作量來劃分正蛙，還可以將排序方法分為簡單排序法督弓、先進排序法、基數(shù)排序法3類乒验。如果按照排序過程中采用的策略不同愚隧，還可以將排序歸納為插入排序、選擇排序锻全、交換排序狂塘、歸并排序、基數(shù)排序幾類鳄厌。
內(nèi)排序的方法雖然很多荞胡，但就其全面性而言，很難說哪一種或者哪一類方法最好了嚎，每一種方法都有它自己的優(yōu)勢和不足泪漂，使用者應(yīng)該根據(jù)不同的環(huán)境和情況（如參加排序的序列數(shù)量的大小或者序列的初始狀態(tài)等）選擇較為合適的方法。
無論何種排序方法歪泳，衡量其性能的主要指標(biāo)不外乎兩個：其一萝勤、執(zhí)行排序算法所需要的時間；另一個呐伞，執(zhí)行排序算法所需要的附加空間敌卓。
對于前者，排序過程中要進行的基本動作包括：1荸哟、比較兩個元素的大小假哎，2、將元素從一個位置移動到另一個位置（采用鏈表排序時可以不必移動元素）鞍历。因此舵抹，排序的工作量取決于這兩種動作的執(zhí)行次數(shù)，尤其是前一個動作劣砍。
下面具體來介紹幾種內(nèi)排序方法
各種內(nèi)排序方法的比較
各種排序算法之間的比較主要從下面幾個方面綜合考慮惧蛹。
- 算法的時間復(fù)雜度
- 算法的空間復(fù)雜度
- 排序穩(wěn)定性
- 算法結(jié)構(gòu)的復(fù)雜度
- 參加排序的數(shù)據(jù)規(guī)模
穩(wěn)定性比較
插入排序、泡排序刑枝、二路歸并排序香嗓、基數(shù)排序 方法是穩(wěn)定排序方法。
選擇排序装畅、謝爾排序靠娱、快速排序、堆積排序 方法是不穩(wěn)定排序方法掠兄。
復(fù)雜性比較
各種內(nèi)排序算法的時間復(fù)雜度和空間復(fù)雜度如下表所列：
排序方法 平均時間 最壞情況 輔助空間
插入排序 O(n2) O(n2) O(1)
謝爾排序 O(nlog2n) O(nlog2n) O(1)
冒泡排序 O(n2) O(n2) O(1)
快速排序 O(nlog2n) O(n2) O(log2n)
選擇排序 O(n2) O(n2) O(1)
堆積排序 O(nlog2n) O(nlog2n) O(1)
歸并排序 O(nlog2n) O(nlog2n) O(n)
基數(shù)排序 O(d(n+r)) O(d(n+r)) O(n+r)
綜上所述像云，得出如下結(jié)論：
- 在平均情況下锌雀，謝爾排序、快速排序迅诬、堆積排序腋逆、歸并排序 都能達到較快的排序速度。進一步可知侈贷，快速排序最快惩歉。從空間消費來看，堆積排序最省俏蛮。
- 在平均情況下撑蚌，插入排序、冒泡排序方法的排序速度較慢搏屑，但當(dāng)參加排序的序列開始就局部有序時锨并，這兩種排序方法能達到較快的排序速度。最好情況下睬棚，時間復(fù)雜度為O(n)，比情況1中敘述的4種方法要好一些解幼，而且這兩種方法輔助空間消費較少抑党。所以當(dāng)n較小、或者序列開始就局部有序時撵摆，可選擇這兩種方法底靠。多數(shù)情況下可以根據(jù)不同情況與1中的4種方法結(jié)合使用。
- 基數(shù)排序方法消費的空間較多特铝，但其時間復(fù)雜度可簡化成O(dn)暑中；當(dāng)元素的位數(shù)較少時，可進一步簡化成O(n)鲫剿， 在這種情況下也能達到較快的排序速度鳄逾。另外，歸并愛旭方法也需要的輔助空間較多灵莲。
- 從算法結(jié)構(gòu)的簡單性來看雕凹，插入排序法、選擇排序法政冻、冒泡排序法 比較簡單和直接枚抵；而謝爾排序法、快速排序法明场、堆積排序法汽摹、歸并排序法 都可以看做是對某一種排序法的進一步改進。相對而言苦锨，改進后的排序法所對應(yīng)的算法可能都比較復(fù)雜逼泣。
- 從參加排序的數(shù)據(jù)序列的規(guī)模大小來看趴泌，n越小，采用簡單排序方法就越合適圾旨；n越大踱讨，采用改進的排序方法越合適。這是因為n越小砍的，n2與log2n的差距越小痹筛，并且簡單排序方法的時間復(fù)雜度的系數(shù)均小于1（泡排序法的最壞情況以外），而改進后的排序方法的時間復(fù)雜度的系數(shù)均大于1廓鞠，因而也使得他們之間的差距變小帚稠。
從上面的分析可以看到，很難說哪一個排序方法絕對好床佳。每一種排序方法都有其優(yōu)缺點滋早，適合于在不同的環(huán)境下使用。因此在實際應(yīng)用中砌们，要根據(jù)具體情況選擇合乎實際情況的方法杆麸。下面給出綜合考慮以上幾方面后所得出的大致結(jié)論，僅供在選擇內(nèi)排序方法是參考：
- 當(dāng)參加排序的數(shù)據(jù)規(guī)模n較大浪感，關(guān)鍵字元素分布比較隨機昔头，并且不要求排序穩(wěn)定性時，宜選用快速排序法影兽。
- 當(dāng)參加排序的數(shù)據(jù)規(guī)模n較大揭斧，內(nèi)存空間又允許，并且有排序穩(wěn)定性要求峻堰，宜采用歸并排序法讹开。
- 當(dāng)參加排序的數(shù)據(jù)規(guī)模n較大，元素分布可能出現(xiàn)升序或者逆序的情況捐名，并且對排序穩(wěn)定性不要求時旦万，宜采用堆積排序方法或者歸并排序方法。
- 當(dāng)參加排序的數(shù)據(jù)規(guī)模n較邢馓！（如小于100）纸型，元素基本有序（升序），或者分布也比較隨機梅忌，并且有排序穩(wěn)定要求時狰腌，宜采用插入排序方法。
- 當(dāng)參加排序的數(shù)據(jù)規(guī)模n較小牧氮，對排序穩(wěn)定性又不要求時琼腔，宜采用選擇排序方法。
向插入排序踱葛、選擇排序丹莲、歸并排序 都比較容易在鏈表上實現(xiàn)光坝，避免將大量時間花費在元素的位置移動上。像快速排序甥材、堆積排序就很難在鏈表上實現(xiàn)盯另。
外排序
(待完成)
