基数排序

/*********************\
 * 基数排序（桶排序）* 
\*********************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

//struct of node
typedef struct node{
        int num;
        struct node * next;
}NODE;
        
/*!<链表尾部添加节点*/
void addnode(NODE * head,int num)
{
     NODE * temp = head;
     while(temp->next)temp=temp->next;
     NODE * newnode = (NODE*)malloc(sizeof(NODE));
     newnode->next = NULL;
     newnode->num = num;
     temp->next=newnode;   
}

/*!<释放所有链表空间*/
void freelist(NODE * head)
{
     NODE * temp;
     while(head)
     {
         temp = head;
         head = head->next;
         free(temp);
     }
}
/*!<清空链表，只留表头*/ 
void clearlist(NODE * head)
{
     NODE * p = head->next;
     NODE * q;
     head->next = NULL;
     while(p)
     {
        q = p;
        p = p->next;
        free(q);
     }
}
/*!<打印链表数据*/
void printlist(NODE * head)
{
     NODE * temp = head->next;
     while(temp)
     {
         printf("->%d",temp->num);
         temp=temp->next;
     }
     putchar('\n');
}

/*!<基数排序函数*/ 
void RadixSort(int a[],int bass,int n)
{
     int max = 0,i,j,k=0,iTemp,sort_times; 
     NODE ** barrel;
     
     //确定排序趟数
     for(i=0;i<n;i++)
         if(a[i]>max)max=a[i];
     for(sort_times=0;pow(bass,sort_times)<max;sort_times++);
     
      barrel = (NODE**)malloc(bass*sizeof(NODE*));
     //初始化桶
     for(i=0;i<bass;i++)
     {
         NODE * node = (NODE*)malloc(sizeof(NODE));
         node->next = NULL;
         barrel[i]=node;                    
     }
     //排序 
     for(i=0;i<sort_times;i++)
     {
                            
         for(j=0;j<n;j++)
         {
             iTemp = a[j]%(int)round(pow(bass,i+1));
             iTemp = iTemp/(int)round(pow(bass,i));
             addnode(barrel[iTemp],a[j]);
         }
         
         //打印桶内数据 
         printf("第 %d 趟排序桶内数据情况:\n",i);
         for(j=0;j<bass;j++)
         {
             printf("barrel[%d]",j);
             printlist(barrel[j]);
         }
         
          
         for(j=0,k=0;j<bass;j++)
         {
             NODE * temp=barrel[j]->next;
             while(temp)
             {
                 a[k++]=temp->num;
                 temp=temp->next;
                 if(k>n) break;
             }
         }
         
         //打印每趟排序后的结果 
         printf("第 %d 趟排序后队列情况:\n",i);
         for(j=0;j<n;j++)
         {
             printf("%d ",a[j]);     
         } 
         putchar('\n');
         
         //清空桶 
         for(j=0;j<bass;j++) clearlist(barrel[j]);
     }
     //释放空间 
     for(i=0;i<bass;i++) freelist(barrel[i]);   
}

/*!< func main*/ 
int  main(void)
{
     int i = 0,n,bass;
     int a[] = {1,6,2,8,3,25,66,7,3,5,634,633,643,2465,2355,2120};
     n=sizeof(a)/sizeof(int);
     
     printf("请输入基数排序的基数:\n");
     scanf("%d",&bass); 
     
     printf("--排序前--: \n"); 
     for(i=0;i<n;i++) printf(" %d ",a[i]);      
     putchar('\n');
     
     RadixSort(a,bass,n);
     
     printf("--排序后--: \n");  
     for(i=0;i<n;i++)printf(" %d ",a[i]);     
     putchar('\n');
      
     system("pause");
     return 0;      
} 

 

 

 

执行情况：

 

请输入基数排序的基数:
10
--排序前--:
 1  6  2  8  3  25  66  7  3  5  634  633  643  2465  2355  2120
第 0 趟排序桶内数据情况:
barrel[0]->2120
barrel[1]->1
barrel[2]->2
barrel[3]->3->3->633->643
barrel[4]->634
barrel[5]->25->5->2465->2355
barrel[6]->6->66
barrel[7]->7
barrel[8]->8
barrel[9]
第 0 趟排序后队列情况:
2120 1 2 3 3 633 643 634 25 5 2465 2355 6 66 7 8
第 1 趟排序桶内数据情况:
barrel[0]->1->2->3->3->5->6->7->8
barrel[1]
barrel[2]->2120->25
barrel[3]->633->634
barrel[4]->643
barrel[5]->2355
barrel[6]->2465->66
barrel[7]
barrel[8]
barrel[9]
第 1 趟排序后队列情况:
1 2 3 3 5 6 7 8 2120 25 633 634 643 2355 2465 66
第 2 趟排序桶内数据情况:
barrel[0]->1->2->3->3->5->6->7->8->25->66
barrel[1]->2120
barrel[2]
barrel[3]->2355
barrel[4]->2465
barrel[5]
barrel[6]->633->634->643
barrel[7]
barrel[8]
barrel[9]
第 2 趟排序后队列情况:
1 2 3 3 5 6 7 8 25 66 2120 2355 2465 633 634 643
第 3 趟排序桶内数据情况:
barrel[0]->1->2->3->3->5->6->7->8->25->66->633->634->643
barrel[1]
barrel[2]->2120->2355->2465
barrel[3]
barrel[4]
barrel[5]
barrel[6]
barrel[7]
barrel[8]
barrel[9]
第 3 趟排序后队列情况:
1 2 3 3 5 6 7 8 25 66 633 634 643 2120 2355 2465
--排序后--:
 1  2  3  3  5  6  7  8  25  66  633  634  643  2120  2355  2465
请按任意键继续. . .