最近在看《算法導論》，首先在這推薦一下這本書，寫的確實很精彩
。
《算法導論》的第二部分分析了多種排序算法。包括插入排序、歸并排序、堆排序、快速排序以及線性排序的幾個算法。
下面簡要總結一下。
對于輸入規模為n的數組。插入排序的復雜度為O(n^2)。
歸并排序、堆排序、快速排序的復雜度為O(n㏒n);
線性排序的復雜度為O(n)
1.插入排序的性能和輸入元素的的序列有很大的關系，如果輸入已排序的序列，則復雜度是線性的，若輸入是逆序的則是O(n^2)的。
2.堆排序用到了優先隊列（優先隊列是一種用來維護由一組元素構成的集合S的數據結構）。
3.快速排序的關鍵是主元的選取(pivot)。在排序過程中元素被分成四部分：小于等于主元的序列、大于主元的序列、未比較的序列、主元。
當未比較的序列未空時，再分別對小于等于主元的序列進行排序、對大于主元的序列進行排序。
以上三種排序都是原地排序。所謂的原地排序(in-place)是指這些元素是在原數組中重排序的，在任何時刻，至多其中的常數個數字是存儲在數組之外的。
4.歸并排序是將原數組劃分成子序列，對子序列進行排序，然后將排序好的子序列合并到一起從而使得原序列重排。
歸并排序不是原地排序，它需要額外的內存資源。
以上四種是比較常用的排序，對于輸入序列沒有特殊的要求，并且都是比較排序，也就是說通過比較各個元素而進行的排序。它們的時間復雜度最好為O(n㏒n);
下面介紹能在時間內完成的排序。
1.計數排序
適用條件：輸入序列中的元素取值在一個范圍之內0-k
基本思想:對于每一個元素確定比它小的的元素的個數。
排序A序列，將結果放入B中，元素的取值范圍為0-k
偽代碼如下：
Count-sort(A,B,k)
for i=0 to k
do C[i]=0
for j=1 to length(A)
do C[A[j]] = C[A[j]]+1;計算A[j]的個數。
for i=1 to k
do C[i] = C[i-1]+C[i];計算小于和等于i的元素個數
for j=length(A) downto 1
do B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]]-1;
我們可以明顯看到計數排序不是原地排序。同時計數排序是穩定的（即相同的元素輸入和輸出的相對位置不變。）