【 聲明:版權所有,歡迎轉載,請勿用於商業用途。 聯系信箱:feixiaoxing @163.com】
基數排序是另外一種比較有特色的排序方式,它是怎麼排序的呢?我們可以按照下面的一組數字做出說明: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)計算在某一分位上的數據
int pre_process_data(int array[], int length, int weight)
{
int index ;
int value = 1;
for(index = 0; index < weight; index++)
value *= 10;
for(index = 0; index < length; index ++)
array[index] = array[index] % value /(value /10);
for(index = 0; index < length; index ++)
if(0 != array[index])
return 1;
return 0;
}
int pre_process_data(int array[], int length, int weight)
{
int index ;
int value = 1;
for(index = 0; index < weight; index++)
value *= 10;
for(index = 0; index < length; index ++)
array[index] = array[index] % value /(value /10);
for(index = 0; index < length; index ++)
if(0 != array[index])
return 1;
return 0;
} b)對某一分位上的數據按照0~10排序
void sort_for_basic_number(int array[], int length, int swap[])
{
int index;
int basic;
int total = 0;
for(basic = -9; basic < 10; basic++){
for(index = 0; index < length; index++){
if(-10 != array[index] && basic == array[index] ){
swap[total ++] = array[index];
array[index] = -10;
}
}
}
memmove(array, swap, sizeof(int) * length);
}
void sort_for_basic_number(int array[], int length, int swap[])
{
int index;
int basic;
int total = 0;
for(basic = -9; basic < 10; basic++){
for(index = 0; index < length; index++){
if(-10 != array[index] && basic == array[index] ){
swap[total ++] = array[index];
array[index] = -10;
}
}
}
memmove(array, swap, sizeof(int) * length);
}
c)根據b中的排序結果,對實際的數據進行排序
void sort_data_by_basic_number(int array[], int data[], int swap[], int length, int weight)
{
int index ;
int outer;
int inner;
int value = 1;
for(index = 0; index < weight; index++)
value *= 10;
for(outer = 0; outer < length; outer++){
for(inner = 0; inner < length; inner++){
if(-10 != array[inner] && data[outer]==(array[inner] % value /(value/10))){
swap[outer] = array[inner];
array[inner] = -10;
break;
}
}
}
memmove(array, swap, sizeof(int) * length);
return;
}
void sort_data_by_basic_number(int array[], int data[], int swap[], int length, int weight)
{
int index ;
int outer;
int inner;
int value = 1;
for(index = 0; index < weight; index++)
value *= 10;
for(outer = 0; outer < length; outer++){
for(inner = 0; inner < length; inner++){
if(-10 != array[inner] && data[outer]==(array[inner] % value /(value/10))){
swap[outer] = array[inner];
array[inner] = -10;
break;
}
}
}
memmove(array, swap, sizeof(int) * length);
return;
}
d)把a、b、c組合起來構成基數排序,直到某一分位上的數據為0
void radix_sort(int array[], int length)
{
int* pData;
int weight = 1;
int count;
int* swap;
if(NULL == array || 0 == length)
return;
pData = (int*)malloc(sizeof(int) * length);
assert(NULL != pData);
memmove(pData, array, length * sizeof(int));
swap = (int*)malloc(sizeof(int) * length);
assert(NULL != swap);
while(1){
count = pre_process_data(pData, length, weight);
if(!count)
break;
sort_for_basic_number(pData, length, swap);
sort_data_by_basic_number(array, pData, swap, length, weight);
memmove(pData, array, length * sizeof(int));
weight ++;
}
free(pData);
free(swap);
return;
}
void radix_sort(int array[], int length)
{
int* pData;
int weight = 1;
int count;
int* swap;
if(NULL == array || 0 == length)
return;
pData = (int*)malloc(sizeof(int) * length);
assert(NULL != pData);
memmove(pData, array, length * sizeof(int));
swap = (int*)malloc(sizeof(int) * length);
assert(NULL != swap);
while(1){
count = pre_process_data(pData, length, weight);
if(!count)
break;
sort_for_basic_number(pData, length, swap);
sort_data_by_basic_number(array, pData, swap, length, weight);
memmove(pData, array, length * sizeof(int));
weight ++;
}
free(pData);
free(swap);
return;
}
總結:
(1)測試的時候注意負數的情形
(2)如果在某一位數據相同,那麼需要考慮上一輪數據排序的情況
(3)代碼中多次分配小空間,此處代碼待優化
補充:
(1)10月15日晚上修改了余數取值范圍,這樣負數也可以參加排序
(2)10月16日上午增加了一個swap內存分配,避免了內存的重復分配和釋放
(3)10月16日上午刪除了count計數,一旦發現有不等於0的數據直接返回為1,不需要全部遍歷數據