一步一步寫算法（之基數排序）

2021-11-13 05:26:28

基數排序是另外一種比較有特色的排序方式，它是怎麼排序的呢？我們可以按照下面的一組數字做出說明：12、 104、 13、 7、 9

（1）按個位數排序是12、13、104、7、9

（2）再根據十位排序104、7、9、12、13

（3）再根據百位排序7、9、12、13、104

這裡注意，如果在某一位的數字相同，那麼排序結果要根據上一輪的數組确定，舉個例子來說：07和09在十分位都是0，但是上一輪排序的時候09是排在07後面的；同樣舉一個例子，12和13在十分位都是1，但是由于上一輪12是排在13前面，是以在十分位排序的時候，12也要排在13前面。

是以，一般來說，10基數排序的算法應該是這樣的？

（1）判斷資料在各位的大小，排列資料；

（2）根據1的結果，判斷資料在十分位的大小，排列資料。如果資料在這個位置的餘數相同，那麼資料之間的順序根據上一輪的排列順序确定；

（3）依次類推，繼續判斷資料在百分位、千分位......上面的資料重新排序，直到所有的資料在某一分位上資料都為0。

說了這麼多，寫上我們的代碼。也希望大家自己可以試一試。

a）計算在某一分位上的資料

b）對某一分位上的資料按照0~10排序

c）根據b中的排序結果，對實際的資料進行排序

d）把a、b、c組合起來構成基數排序，直到某一分位上的資料為0

總結：

（1）測試的時候注意負數的情形

（2）如果在某一位資料相同，那麼需要考慮上一輪資料排序的情況

（3）代碼中多次配置設定小空間，此處代碼待優化

補充：

（1） 10月15日晚上修改了餘數取值範圍，這樣負數也可以參加排序

（2）10月16日上午增加了一個swap記憶體配置設定，避免了記憶體的重複配置設定和釋放

（3）10月16日上午删除了count計數，一旦發現有不等于0的資料直接傳回為1，不需要全部周遊資料

繼續閱讀