這一段時(shí)間都在看TAOCP的排序算法，這些都是我大學(xué)生活里面很想看卻沒看到的部分，同時(shí)也為了鞏固實(shí)踐，把它們都寫出程序來了。供自己復(fù)習(xí)之用，也希望能與網(wǎng)友分享。如果有什么問題，還請(qǐng)各位網(wǎng)友能夠指正出來。
一、計(jì)數(shù)排序（位于TAOCP第三卷中的內(nèi)部排序前面的內(nèi)容中，是高德納先生講的第一種類型的排序方法，其適應(yīng)面比較窄，但卻是很有效。同時(shí)可以證明此算法是穩(wěn)定的）
//?a數(shù)組存儲(chǔ)輸入數(shù)據(jù)，count數(shù)組用來計(jì)數(shù)
for(int?i=0;?i<N-1;?i++)?{
????for(int?j=i+1;?j<N;?j++)?{
?????????if(a[i]?>?a[j])?{
?????????????count[i]?++;????????
?????????}?else?{
?????????????count[j]?++;???????
?????????}
????}????????
}
//?b數(shù)組用于存儲(chǔ)排序后的數(shù)據(jù)
for(int?i=0;?i<N;?i++)?{
????b[count[i]]?=?a[i];
}
如果說上面的程序?qū)儆凇氨容^計(jì)數(shù)”[引自TAOCP]的話，那么還有一種方法就是“分布計(jì)數(shù)”[引自TAOCP]了。
for(int?i=0;?i<N;?i++)?{
????count[a[i]-1]?++;
}
for(int?i=u;?i<v;?i++)?{
????count[i]?+=?count[i-1];????????????//?其中count[v-1]=N，且count的下標(biāo)從u-1至v-1?
}
for(int?i=N-1;?i>=0;?i--)?{
????b[count[a[i]-1]-1]?=??a[i];?????//?b的下標(biāo)從0至N-1?
????count[a[i]-1]?--;
}
需要注意的是，在“分布計(jì)數(shù)”中的count與“比較計(jì)數(shù)”中的count的計(jì)數(shù)方式有一點(diǎn)點(diǎn)不同，所以在最終轉(zhuǎn)換成排序后的數(shù)組時(shí)也有不同的處理。而且，在“分布計(jì)數(shù)”中，要求各個(gè)記錄的鍵碼值最好滿足一定的分布條件[u,v]，全都在一個(gè)比較整齊的區(qū)間內(nèi)。也可以證明，此排序算法是穩(wěn)定的，主要就是在構(gòu)成排序數(shù)組b時(shí)采用的循環(huán)是倒序，如果是順序的話，那就不同了。
二、比較排序（這也是TAOCP書中講的第一類排序方法，也是各類數(shù)據(jù)結(jié)構(gòu)或算法教材必須涉及到的一類算法，過多的解釋就無需展開了，讓我們來直接用程序?qū)υ挕＃?br />
for(int?i=1;?i<N;?i++)?{
????int?r?=?a[i];
????int?j?=?i?-?1;
????while(r?<?a[j]?&&?j?>=?0)?{
????????a[j+1]?=?a[j];
????????j?--;
????}
????a[j+1]?=?r;
}
上面這個(gè)是順序表的直接插入方法，針對(duì)于2~N的各個(gè)記錄，用直接尋找最佳位置的方式來進(jìn)行排序，尋找過程可以和移動(dòng)過程（順序表獨(dú)有）結(jié)合起來，以節(jié)省時(shí)間。在這種方式下，其實(shí)最好采用表方式進(jìn)行存儲(chǔ)。在TAOCP一書中還提到，如果結(jié)合二叉插入或“兩路”插入的方法，可以進(jìn)一步節(jié)省時(shí)間，但是其實(shí)質(zhì)上還是會(huì)得不到最終的改善。
int?h[4]?=?{8,?4,?2,?1};???????//?shell排序每步步長(zhǎng)?
for(int?ih=0;?ih<4;?ih++)?{
????for(int?i=h[ih];?i<N;?i+=h[ih])?{
????????int?r?=?a[i];
????????int?j?=?i?-?h[ih];
????????while(r?<?a[j]?&&?j>=0)?{
????????????a[j+h[ih]]?=?a[j];
????????????j?-=?h[ih];???????????
????????}
????????a[j+h[ih]]?=?r;
????}
}
結(jié)合多步長(zhǎng)跳躍方式和直接插入方法，就構(gòu)成了Shell排序方法，也叫做“減少增量的排序”[引自TAOCP]。選擇一個(gè)較好的增量序列來作為步長(zhǎng)，在上述程序中就是h數(shù)組，優(yōu)點(diǎn)是對(duì)直接插入方法會(huì)有實(shí)質(zhì)性的改進(jìn)。
int?t?=?N-1;??//??已經(jīng)排好序的最低元素下標(biāo)-1?
int?temp;
int?s;
while(t?!=?0)?{
????s?=?t;
????t?=?0;
????for(int?i=0;?i<s;?i++)?{?????//?如果t以上的元素都已經(jīng)排好序，則無需再排序了?
????????if(a[i]?>?a[i+1])?{
????????????temp?=?a[i];
????????????a[i]?=?a[i+1];
????????????a[i+1]?=?temp;
????????????t?=?i;
????????}
????}
}
上面這個(gè)程序是冒泡排序方法，在TAOCP書中講是第二類排序算法，通過“交換”或“換位”方法來實(shí)現(xiàn)。在程序中，t變量是相當(dāng)于選擇最后（假設(shè)每一次都是把大元素往后移動(dòng)）還要排序元素的下標(biāo)，因此對(duì)于t以后的元素就無須再去比較和考察了。因此，冒泡排序也可稱為“交換選擇”或“擴(kuò)散”等。
因?yàn)榭磿倪M(jìn)度比較慢，這些程序就是我先根據(jù)算法原理實(shí)現(xiàn)了的。后續(xù)還有很多排序和查找算法，我還要進(jìn)一步學(xué)習(xí)。同時(shí)，有關(guān)這些算法的優(yōu)缺點(diǎn)和分析需要做進(jìn)一步探討，歡迎各位網(wǎng)友能與多一起學(xué)習(xí)這等重要基礎(chǔ)性知識(shí)。我的郵箱地址是：tanzek@gmail.com