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