C語言實(shí)現(xiàn)簡單的基數(shù)排序

　　C語言實(shí)現(xiàn)簡單的基數(shù)排序

　　八大排序算法有：冒泡排序、插入排序、選擇排序、快速排序、希爾排序、堆排序、歸并排序、基數(shù)排序。前面七種網(wǎng)上都有很多例子，但是最后一種基數(shù)排序卻很少看到，所以我總結(jié)了一下，并且自己寫了一個(gè)簡單的實(shí)現(xiàn)。

　　基數(shù)排序是一種分配排序，其基本思想是：排序過程無須比較關(guān)鍵字，而是通過“分配”和“收集”過程來實(shí)現(xiàn)排序。它們的時(shí)間復(fù)雜度可達(dá)到線性O(shè)（n）?；鶖?shù)排序所做的事情，是對N位分別進(jìn)行排序。從直覺上來看，人們可能會覺得應(yīng)該首先按最高有效位進(jìn)行排序，不過這點(diǎn)與我們的直覺相反，基數(shù)排序首先對最低有效位數(shù)字進(jìn)行排序。如果我們每次比較r bits，則需要進(jìn)行b/r趟，每趟進(jìn)行計(jì)數(shù)排序需要O（n+2^r），則總的時(shí)間復(fù)雜度為O（b/r（n+2^r））。

　　理論上來說，基數(shù)排序的速度是以上幾種排序方法中最快的，可以達(dá)到O（N），而其它的排序算法最快也只有O（N*logN）。但是，基數(shù)排序需要占用額外的空間，而且只支持整數(shù)進(jìn)行排序。

　　實(shí)現(xiàn)代碼如下：

　　#include

　　#include

　　/* 獲取輸入數(shù)字的索引值，dec指定數(shù)字的位數(shù)，3代表百位數(shù)，order指定需要獲取哪一位的索引，1代表個(gè)位，2代表十位，3代表百位 */

　　int get_index（int num， int dec， int order）

　　{

　　int i， j， n;

　　int index;

　　int div;

　　/* 根據(jù)位數(shù)，循環(huán)減去不需要的高位數(shù)字 */

　　for （i=dec; i>order; i--） {

　　n = 1;

　　for （j=0; j

　　n *= 10;

　　div = num/n;

　　num -= div * n;

　　dec--;

　　}

　　/* 獲得對應(yīng)位數(shù)的整數(shù) */

　　n = 1;

　　for （i=0; i

　　n *= 10;

　　/* 獲取index */

　　index = num / n;

　　return index;

　　}

　　/* 進(jìn)行基數(shù)排序 */

　　void radix_sort（int array［］， int len， int dec， int order）

　　{

　　int i， j;

　　int index; /* 排序索引 */

　　int tmp［len］; /* 臨時(shí)數(shù)組，用來保存待排序的中間結(jié)果 */

　　int num［10］; /* 保存索引值的數(shù)組 */

　　memset（num， 0， 10*sizeof（int））; /* 數(shù)組初始清零 */

　　memset（tmp， 0， len*sizeof（int））; /* 數(shù)組初始清零 */

　　if （dec < order） /* 最高位排序完成后返回 */

　　return;

　　for （i=0; i

　　index = get_index（array［i］， dec， order）; /* 獲取索引值 */

　　num［index］++; /* 對應(yīng)位加一 */

　　}

　　for （i=1; i<10; i++）

　　num［i］ += num［i-1］; /* 調(diào)整索引數(shù)組 */

　　for （i=len-1; i>=0; i--） {

　　index = get_index（array［i］， dec， order）; /* 從數(shù)組尾開始依次獲得各個(gè)數(shù)字的索引 */

　　j = --num［index］; /* 根據(jù)索引計(jì)算該數(shù)字在按位排序之后在數(shù)組中的位置 */

　　tmp［j］ = array［i］; /* 數(shù)字放入臨時(shí)數(shù)組 */

　　}

　　for （i=0; i

　　array［i］ = tmp［i］; /* 從臨時(shí)數(shù)組復(fù)制到原數(shù)組 */

　　printf（“the %d time\n”， order）;

　　for （i=0; i<30; i++）

　　printf（“%d ”， array［i］）;

　　printf（“\n”）;

　　/* 繼續(xù)按高一位的數(shù)字大小進(jìn)行排序 */

　　radix_sort（array， len， dec， order+1）;

　　return;

　　}

　　int main（int argc， char *argv［］）

　　{

　　int i;

　　int array［30］ = {258， 976， 515， 337， 359， 701， 916， 494， 303， 175，

　　677， 825， 131， 560， 147， 254， 759， 814， 917， 382，

　　452， 114， 873， 585， 881， 127， 819， 658， 461， 435};

　　int len = 30; /* 測試數(shù)據(jù)個(gè)數(shù) */

　　int dec = 3; /* 數(shù)據(jù)位數(shù)，3代表3位數(shù) */

　　int order = 1; /* 排序的位數(shù)，1代表個(gè)位、2代表十位、3代表百位 */

　　printf（“before\n”）;

　　for （i=0; i<30; i++）

　　printf（“%d ”， array［i］）;

　　printf（“\n”）;

　　/* 排序函數(shù)，從個(gè)位開始 */

　　radix_sort（array， len， dec， order）;

　　printf（“final\n”）;

　　for （i=0; i<30; i++）

　　printf（“%d ”， array［i］）;

　　printf（“\n”）;

　　return 0;

　　}

　　運(yùn)行結(jié)果如下：

　　baishen@sjtu：~/sort$ 。/radix

　　before

　　258 976 515 337 359 701 916 494 303 175 677 825 131 560 147 254 759 814 917 382 452 114 873 585 881 127 819 658 461 435

　　the 1 time

　　560 701 131 881 461 382 452 303 873 494 254 814 114 515 175 825 585 435 976 916 337 677 147 917 127 258 658 359 759 819

　　the 2 time

　　701 303 814 114 515 916 917 819 825 127 131 435 337 147 452 254 258 658 359 759 560 461 873 175 976 677 881 382 585 494

　　the 3 time

　　114 127 131 147 175 254 258 303 337 359 382 435 452 461 494 515 560 585 658 677 701 759 814 819 825 873 881 916 917 976

　　final

　　114 127 131 147 175 254 258 303 337 359 382 435 452 461 494 515 560 585 658 677 701 759 814 819 825 873 881 916 917 976