#include<iostream.h> 
#include<malloc.h> 
 
typedef struct node{ 
 int key; 
 struct node * next; 
}KeyNode; 
 
void inc_sort(int keys[],int size,int bucket_size){ 
 KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); 
 for(int i=0;i<bucket_size;i++){ 
  bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode)); 
  bucket_table[i]->key=0; //记录当前桶中的数据量 
  bucket_table[i]->next=NULL; 
 } 
 for(int j=0;j<size;j++){ 
  KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode)); 
  node->key=keys[j]; 
  node->next=NULL; 
  //映射函数计算桶号 
  int index=keys[j]/10; 
  //初始化P成为桶中数据链表的头指针 
  KeyNode *p=bucket_table[index]; 
  //该桶中还没有数据 
  if(p->key==0){ 
   bucket_table[index]->next=node; 
   (bucket_table[index]->key)++; 
  }else{ 
   //链表结构的插入排序 
   while(p->next!=NULL&&p->next->key<=node->key) 
    p=p->next;  
   node->next=p->next; 
   p->next=node; 
   (bucket_table[index]->key)++; 
  } 
 } 
 //打印结果 
 for(int b=0;b<bucket_size;b++) 
  for(KeyNode *k=bucket_table[b]->next; k!=NULL; k=k->next) 
   cout<<k->key<<" "; 
 cout<<endl; 
} 
 
void main(){ 
 int raw[]={49,38,65,97,76,13,27,49};  
 int size=sizeof(raw)/sizeof(int);  
 inc_sort(raw,size,10); 
}