所謂排序，就是要整理檔案中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。
排序是資料進行中經常使用的一種重要運算。在計算機及其應用系統中，花費在排序上的時間在系統運作時間中占有很大比重，并且排序本身對推動算法分析的發展也起很大作用。目前已有上百種排序方法，但并沒有一個萬能的排序方法來解決所有問題，接下來介紹幾種常用的排序方法，并對它們進行分析和比較。
1．按是否涉及資料的内、外存交換
内排序
在排序過程中，若整個檔案都是放在記憶體中處理，排序時不涉及資料的内、外存交換，則稱之為内部排序。
外排序
若排序過程中要進行資料的内、外存交換，則稱之為外部排序。
2．按政策劃分内部排序方法
插入排序
選擇排序
交換排序
歸并排序
配置設定排序
評價排序算法好壞的标準主要有兩條：
執行時間和所需的輔助空間
算法本身的複雜程度
排序算法的時間複雜度：
大多數排序算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序算法其執行時間不僅依賴于問題的規模，還取決于輸入執行個體中資料的狀态。
排序算法的空間複雜度：
若排序算法所需的輔助空間并不依賴于問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。非就地排序一般要求的輔助空間為O(n)。
插入排序(Insertion Sort)的基本思想是：每次将一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子檔案中的适當位置，直到全部記錄插入完成為止。
常用的插入排序：直接插入排序 和希爾排序。
1.直接插入排序
排序過程中每次從無序表中取出第一個元素，将它插入到有序表中的适當位置，使之成為新的有序表，重複n-1次可完成排序過程。
時間複雜度為O（n^2），空間複雜度為O（1），穩定的。
僞碼：
2.希爾排序
希爾排序（Shell Sort）又稱為“縮小增量排序”。是1959年由D.L.Shell提出來的。該方法先将整個待排元素序列分割成若幹個子序列（由相隔某個“增量”的元素組成的）分别進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的。
在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組内直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使檔案較接近于有序狀态，是以新的一趟排序過程也較快。
希爾排序是不穩定的。
交換排序是通過兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。
應用交換排序基本思想的主要排序方法有：冒泡排序和快速排序。
1.冒泡排序
将被排序的記錄數組S[1..n]垂直排列，每個記錄s[i]看作是重量為s[i]的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組s：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反複進行，直到最後任何兩個氣泡都是輕者在上，重者在下為止。
平均時間複雜度為O（n^2），空間複雜度為O（1），由于是交換式的是以穩定。
代碼：
2.快速排序
設目前待排序的無序區為S[low..high]，利用分治法可将快速排序的基本思想描述為：
①分解：
在S[low..high]中任選一個記錄作為基準(Pivot)，以此基準将目前無序區劃分為左、右兩個較小的子區間S[low..pivotpos-1)和S[pivotpos+1..high]，并使左邊子區間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正确的位置(pivotpos)上，它無須參加後續的排序。
注意：
劃分的關鍵是要求出基準記錄所在的位置pivotpos。劃分的結果可以簡單地表示為(注意pivot=S[pivotpos])：
S[low..pivotpos-1].keys≤S[pivotpos].key≤S[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通過遞歸調用快速排序對左、右子區間S[low..pivotpos-1]和S[pivotpos+1..high]快速排序。
③組合：
因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什麼，可看作是空操作。
在目前無序區中選取劃分的基準關鍵字是決定算法性能的關鍵。
由于快速排序的交換思想，可知它是不穩定的。
它的平均複雜度可以計算出為O（nlogn），空間複雜度為O（1）。
選擇排序通過每一趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排好序的子檔案的最後，直到全部記錄排序完畢。
常用的選擇排序方法有直接選擇排序和堆排序。
1.直接選擇排序
n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
在無序區S[1..n]中選出關鍵字最小的記錄S[k]，将它與無序區的第1個記錄S[1]交換，使S[1..1]和S[2..n]分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。第i趟排序開始時，目前有序區和無序區分别為S[1..i-1]和S[i..n](1≤i≤n-1)。該趟排序從目前無序區中選出關鍵字最小的記錄S[k]，将它與無序區的第1個記錄S[i]交換，使S[1..i]和S[i+1..n]分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
平均時間複雜度為O(n^2)，空間複雜度為O（1）。
由于這個選擇的關系，有可能會把相同元素的相對位置改變，故為不穩定的。
2.堆排序
1.堆的定義
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤
)
2.堆的分類
堆可分為大根堆和小根堆。
根結點(亦稱為堆頂)的關鍵字是堆裡所有結點關鍵字中最小者的堆稱為小根堆。
根結點(亦稱為堆頂)的關鍵字是堆裡所有結點關鍵字中最大者，稱為大根堆。
3.基本思想
通常堆是通過一維數組來實作的。在起始數組為 0 的情形中：
堆的根節點（即堆積樹的最大值）存放在數組位置 1 的地方;
注意：不使用位置 0，否則左子樹永遠為 0[2]
父節點i的左子節點在位置 (2*i);
父節點i的右子節點在位置 (2*i+1);
子節點i的父節點在位置 floor(i/2);
在堆的資料結構中，堆中的最大值總是位于根節點。堆中定義以下幾種操作：
最大堆調整（Max_Heapify）：将堆的末端子結點作調整，使得子結點永遠小于父結點
建立最大堆（Build_Max_Heap）：将堆所有資料重新排序
堆排序（HeapSort）：移除位在第一個資料的根結點，并做最大堆調整的遞歸運算
4.算法複雜度
堆排序的最壞時間複雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數較多，是以堆排序不适宜于記錄數較少的檔案。
堆排序是就地排序，輔助空間為O(1)，它是不穩定的排序方法。
代碼:
歸并排序(Merge Sort)是利用"歸并"技術來進行排序。歸并是指将若幹個已排序的子檔案合并成一個有序的檔案。
1、算法基本思路
設兩個有序的子檔案(相當于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先将它們合并到一個局部的暫存向量R1(相當于輸出堆)中，待合并完成後将R1複制回R[low..high]中。
（1）合并過程
合并過程中，設定i，j和p三個指針，其初值分别指向這三個記錄區的起始位置。合并時依次比較R[i]和R[j]的關鍵字，取關鍵字較小的記錄複制到R1[p]中，然後将被複制記錄的指針i或j加1，以及指向複制位置的指針p加1。
重複這一過程直至兩個輸入的子檔案有一個已全部複制完畢(不妨稱其為空)，此時将另一非空的子檔案中剩餘記錄依次複制到R1中即可。
（2）動态申請R1
實作時，R1是動态申請的，因為申請的空間可能很大，故須加入申請空間是否成功的處理。
平均時間複雜度為O（nlogn），空間複雜度為O（n），穩定的。
代碼：
配置設定排序的基本思想：排序過程無須比較關鍵字，而是通過"配置設定"和"收集"過程來實作排序.它們的時間複雜度可達到線性階：O(n)。
配置設定排序包括桶排序和基數排序。
1.桶排序
桶排序(Bucket Sort)，其基本思想是：設定若幹個桶，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關鍵字等于k的記錄全都裝入到第k個桶裡(配置設定)，然後按序号依次将各非空的箱子首尾連接配接起來(收集)。
箱子的個數取決于關鍵字的取值範圍。
桶排序的平均時間複雜度是線性的，即O(n)。但最壞情況仍有可能是O(n^2)。空間複雜度為O（m+n）。（m為每個桶的值域）
2.基數排序
基數排序(Radix Sort)是當每個桶的值域區間很大時對桶排序的改進。
将一個記錄的值即排序碼拆分為多個部分來進行比較。例如如果要對0~9999之間的整數進行排序，可以先按照千位數字進行桶排序，将所有數字配置設定到10個桶中，接下來，繼續按照桶排序的方法對百位、十位、個位進行排序，這樣，可以完成排序。這種将排序碼拆分為多個字碼分别來進行排序的方法就是基數排序。
本文轉自cococo點點部落格園部落格，原文連結：http://www.cnblogs.com/coder2012/archive/2013/05/26/3088242.html，如需轉載請自行聯系原作者