基數排序

c 基數排序

#include <stdio.h>

#include <stdlib.h>

#include <sys/time.h>

#include <unistd.h>

//計數排序，npRadix為對應的關鍵字序列，nMax是關鍵字的範圍。npData是具體要

//排的資料，nLen是資料的範圍，這裡必須注意npIndex和npData對應的下标要一緻

//也就是說npIndex[1] 所對應的值為npData[1]

int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)

{

//這裡就不用說了，計數的排序。不過這裡為了是排序穩定

//在标準的方法上做了小修改。

int* pnCount = (int*)malloc(sizeof(int)* nMax); //儲存計數的個數

int i = 0;

for (i = 0; i < nMax; ++i)

{

pnCount[i] = 0;

}

for (i = 0; i < nLen; ++i) //初始化計數個數

++pnCount[npIndex[i]];

for (i = 1; i < 10; ++i) //确定不大于該位置的個數。

pnCount[i] += pnCount[i - 1];

int * pnSort = (int*)malloc(sizeof(int) * nLen); //存放零時的排序結果。

//注意：這裡i是從nLen-1到0的順序排序的，是為了使排序穩定。

for (i = nLen - 1; i >= 0; --i)

--pnCount[npIndex[i]];

pnSort[pnCount[npIndex[i]]] = npData[i];

for (i = 0; i < nLen; ++i) //把排序結構輸入到傳回的資料中。

npData[i] = pnSort[i];

free(pnSort); //記得釋放資源。

free(pnCount);

return 1;

}

//基數排序

int RadixSort(int* nPData, int nLen)

//申請存放基數的空間

int* nDataRadix = (int*)malloc(sizeof(int) * nLen);

int nRadixBase = 1; //初始化倍數基數為1

int nIsOk = 0; //設定完成排序為0

//循環，知道排序完成

while (!nIsOk)

nIsOk = 1;

nRadixBase *= 10;

int i = 0;

for (i = 0; i < nLen; ++i)

{

nDataRadix[i] = nPData[i] % nRadixBase;

nDataRadix[i] /= nRadixBase / 10;

if (nDataRadix[i] > 0)

{

nIsOk = 0;

}

}

if (nIsOk) //如果所有的基數都為0，認為排序完成，就是已經判斷到最高位了。

break;

RadixCountSort(nDataRadix, 10, nPData, nLen);

free(nDataRadix);

int main()

int lens = 1000000;

int a[1000000];

for(i = 0; i < lens; i++ )

a[i] = rand();

/*

//測試基數排序。

int nData[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888};

*/

struct timeval tv1, tv2;

double sec = 0;

gettimeofday(&tv1, 0);

RadixSort(a, lens);

gettimeofday(&tv2, 0);

sec = (double)(tv2.tv_sec - tv1.tv_sec) + (double)(tv2.tv_usec - tv1.tv_usec) / 1000000;

printf("time1: %f\n", sec);

for (i = 0; i < 10; ++i)

printf("%d ", a[i]);

printf("\n");

return 0;