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