【アルゴリズム導論】バケツソート

バケツソート
時間複雑度:O(n)
基本思想:配列するシーケンスをnグループに分けて、各グループをそれぞれ並べ替えて、それから合併して、この中に分けて治める思想があります.例の説明:みんなはc言語を学んできっとswitch-case構造を学んだことがあって、最もよくある問題型は成績を分類することですが、ここではそれをランキングします.10人の学生の成績を仮定すると、78,17,39,26,72,94,21,12,23,68である.私たちは成績を先にセグメント(バケツと呼ばれる)に分けて、十分ごとに1セグメントに分けて、全部で10セグメントに分けることができます.その後、各セグメント内でソートを行い、各セグメントのソートは挿入ソートを採用し、最後にマージすればよい.各セグメントの内容は次のとおりです.
バケツ番号バケツ内の要素
           0: 
           1:12 、17
           2:21 、23 、26
           3:39
           4:
           5:
           6:68
           7:72 、 78
           8:
           9:94
具体的なプログラムは以下のように実現される.

#include<stdio.h>  
#include<malloc.h>  
 
void inc_sort(int arrayA[],int size,int bucket_size);

typedef struct node
{  
    int key;  
    struct node * next;  
}KeyNode;  
  

void main()
{  
    int raw[]={78,17,39,26,72,94,21,12,23,68};   
    int size=sizeof(raw)/sizeof(int);     
    inc_sort(raw,size,10);  
}

/****************************************************\
    ：          
  ：      、    
  ： 
\****************************************************/
void inc_sort(int arrayA[],int size,int bucket_size)
{  
    KeyNode **bucket=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); //       ，bucket        
    for(int i=0;i<bucket_size;i++)
	{  
        bucket[i]=(KeyNode *)malloc(sizeof(KeyNode));//        
        bucket[i]->key=0; //          
        bucket[i]->next=NULL;  
    }  

    for(int j=0;j<size;j++)
	{  
        KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));//    
        node->key=arrayA[j];  
        node->next=NULL;  
       
        int index=arrayA[j]/10; //                   
          
        KeyNode *p=bucket[index];//   p              
        
        if(p->key==0)//           
            bucket[index]->next=node;  
   		else
		{  
            //           
            while((p->next!=NULL)&&(p->next->key<=node->key))//            ，      
                p=p->next;                                   //            
            node->next=p->next;  
            p->next=node;        
        } 
		(bucket[index]->key)++;
    }  
    
    for(int i=0;i<bucket_size;i++)  
	{
        for(KeyNode *k=bucket[i]->next; k!=NULL; k=k->next)  
			printf("%d ",k->key); 
	//	printf("
");
	}
    printf("
"); 

	free(bucket);//           
	
}  
  
  

注意:私はvs 2008で実行して、vc 6.0と少し異なって、主に循環体の中の循環変数の作用域で、間違いは循環変数の繰り返し定義に現れます.たとえば、vs 2008またはvs 2010では、プログラムは次のとおりです.
#include void main() { int i=0; for(int i=0;i<5;i++) printf("%d ",i); }
VC 6.0では、次のように変更する必要があります.
#include void main() { int i=0; for(i=0;i<5;i++) printf("%d ",i); }　
原文:http://blog.csdn.net/tengweitw/article/details/9713333
作者:nineheadedbird