今天學(xué)了基數(shù)排序，據(jù)說(shuō)他的時(shí)間復(fù)雜度也是O(n)，他的思路就是：
沒(méi)有計(jì)數(shù)排序那么理想，我們的數(shù)據(jù)都比較集中，都比較大，一般是4，5位。基本沒(méi)有小的數(shù)據(jù)。
那我們的處理很簡(jiǎn)單，你不是沒(méi)有小的數(shù)據(jù)嘛。我給一個(gè)基數(shù)，例如個(gè)位，個(gè)位都是[0-10)范圍內(nèi)的。先對(duì)他進(jìn)行歸類，把小的放上面，大的放下面，然后個(gè)位排好了，在來(lái)看10位，我們也這樣把小的放上面，大的放下面，依次內(nèi)推，直到最高位排好。那么不就排好了嗎？我們只需要做d(基數(shù)個(gè)數(shù))的循環(huán)就可以了。時(shí)間復(fù)雜度相當(dāng)于O(d * n) 因?yàn)閐為常量，例如5位數(shù)，d就是5.所以近似為O(n)的時(shí)間復(fù)雜度。這次自己寫個(gè)案例：
|
最初的數(shù)據(jù)
|
排好個(gè)位的數(shù)據(jù)
|
排好十位的數(shù)據(jù)
|
排好百位的數(shù)據(jù)
|
|
981
|
981
|
725
|
129
|
|
387
|
753
|
129
|
387
|
|
753
|
955
|
753
|
456
|
|
129
|
725
|
955
|
725
|
|
955
|
456
|
456
|
753
|
|
725
|
387
|
981
|
955
|
|
456
|
129
|
387
|
981
|
這里只需循環(huán)3次就出結(jié)果了。
<!--[if !supportLists]-->3. <!--[endif]-->但是注意，我們必須要把個(gè)位排好。但是個(gè)位怎么排呢？這個(gè)是個(gè)問(wèn)題。書上說(shuō)的是一疊一疊的怎么合并，我是沒(méi)有理解的。希望知道的有高手教我一下。
我是用的一個(gè)計(jì)數(shù)排序來(lái)排各位的，然后排十位。效率應(yīng)該也低不到哪里去。呵呵。。
思路就這樣咯。奉上源代碼：
#include <stdio.h>
#include <stdlib.h>
//計(jì)數(shù)排序，npRadix為對(duì)應(yīng)的關(guān)鍵字序列，nMax是關(guān)鍵字的范圍。npData是具體要
//排的數(shù)據(jù)，nLen是數(shù)據(jù)的范圍，這里必須注意npIndex和npData對(duì)應(yīng)的下標(biāo)要一致
//也就是說(shuō)npIndex[1] 所對(duì)應(yīng)的值為npData[1]
int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)
{
//這里就不用說(shuō)了，計(jì)數(shù)的排序。不過(guò)這里為了是排序穩(wěn)定
//在標(biāo)準(zhǔn)的方法上做了小修改。
int* pnCount = (int*)malloc(sizeof(int)* nMax); //保存計(jì)數(shù)的個(gè)數(shù)
for (int i = 0; i < nMax; ++i)
{
pnCount[i] = 0;
}
for (int i = 0; i < nLen; ++i) //初始化計(jì)數(shù)個(gè)數(shù)
{
++pnCount[npIndex[i]];
}
for (int i = 1; i < 10; ++i) //確定不大于該位置的個(gè)數(shù)。
{
pnCount[i] += pnCount[i - 1];
}
int * pnSort = (int*)malloc(sizeof(int) * nLen); //存放零時(shí)的排序結(jié)果。
//注意：這里i是從nLen-1到0的順序排序的，是為了使排序穩(wěn)定。
for (int i = nLen - 1; i >= 0; --i)
{
--pnCount[npIndex[i]];
pnSort[pnCount[npIndex[i]]] = npData[i];
}
for (int i = 0; i < nLen; ++i) //把排序結(jié)構(gòu)輸入到返回的數(shù)據(jù)中。
{
npData[i] = pnSort[i];
}
free(pnSort); //記得釋放資源。
free(pnCount);
return 1;
}
//基數(shù)排序
int RadixSort(int* nPData, int nLen)
{
//申請(qǐng)存放基數(shù)的空間
int* nDataRadix = (int*)malloc(sizeof(int) * nLen);
int nRadixBase = 1; //初始化倍數(shù)基數(shù)為1
bool nIsOk = false; //設(shè)置完成排序?yàn)閒alse
//循環(huán)，知道排序完成
while (!nIsOk)
{
nIsOk = true;
nRadixBase *= 10;
for (int i = 0; i < nLen; ++i)
{
nDataRadix[i] = nPData[i] % nRadixBase;
nDataRadix[i] /= nRadixBase / 10;
if (nDataRadix[i] > 0)
{
nIsOk = false;
}
}
if (nIsOk) //如果所有的基數(shù)都為0，認(rèn)為排序完成，就是已經(jīng)判斷到最高位了。
{
break;
}
RadixCountSort(nDataRadix, 10, nPData, nLen);
}
free(nDataRadix);
return 1;
}
int main()
{
//測(cè)試基數(shù)排序。
int nData[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888};
RadixSort(nData, 10);
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}