算法导论桶排序

算法导论桶排序

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct stbucket
{
int a;
    struct stbucket *next;
}stBucket;

stBucket* insertsort(stBucket *head)
{
if(NULL == head || NULL == head->next)
return head;
    stBucket *first=head->next;
    stBucket *t,*p,*q;
    head->next=NULL;

while(first)
    {
for(t=first,q=head;((q!=NULL) && (q->a<t->a));p=q,q=q->next);
        first=first->next;
if(q==head)
        {
            head=t;
        }
else
        {
            p->next=t;//第一次比较的时候在这边修改了head->next值
        }
        t->next=q;
    }
return head;
}

void bucketsort(int a[],int length)
{
    stBucket * b[10]={0};
int i=0;
for( i=0;i<10;++i)
    {
        stBucket *ptBucket=(stBucket *)malloc(sizeof(stBucket));
        ptBucket->next=NULL;
        b[i]=ptBucket;
    }
for(i=0;i<length;++i)
    {
int idx=0;
int itemp=a[i];
while(itemp/=10)
        {
            idx++;
        }
int pos=(int)(a[i]/(pow(10,idx)))%10;

        stBucket *temp=b[pos];
while(temp->next)
        {
            temp=temp->next;
        }
        stBucket *ptBucket=(stBucket *)malloc(sizeof(stBucket));
        ptBucket->a=a[i];
        ptBucket->next=NULL;
        temp->next=ptBucket;
    }
int index=0;
for(i=0;i<10;++i)
    {
        b[i]->next=insertsort(b[i]->next);
        stBucket *ptTemp=b[i]->next;
while(ptTemp)
        {
if(index<length)
            {
                a[index]=ptTemp->a;
index++;
            }
            ptTemp=ptTemp->next;
        }
    }
}
int main()
{
int a[]={78,17,39,26,72,94,21,12,23,68};
    bucketsort(a,sizeof(a)/sizeof(int));

int i=0;
for(;i<sizeof(a)/sizeof(int);++i)
printf("%d ",a[i]);
return 0;
}