桶排序

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct Node
{
    int key;
    Node *next;

    Node(int k)
    {
        key = k;
        next = NULL;
    }
};

void Insert(Node **phead,int k)
{
    if(*phead == NULL)
    {
        *phead = new Node(k);
    }
    else
    {
        Node *p = *phead;
        Node *q = p->next;
        if(k<p->key)
        {
            *phead = new Node(k);
            (*phead)->next = p;
        }
        else
        {
            while(q!=NULL && k>q->key)
            {
                p=q;
                q=p->next;
            }
            p->next = new Node(k);
            p->next->next = q;
        }
    }
}

void BucketSort(int *A,int len)
{
    int BucketNum = 10;
    Node **B = new Node*[BucketNum];
    for(int i=0;i<BucketNum;i++)
    {
        B[i] = NULL;
    }
    for(int i=0;i<len;i++)
    {
        Insert(&B[A[i]/10],A[i]);
    }
    int k=0;
    for(int i=0;i<BucketNum;i++)
    {
        Node *p = B[i];
        while(p!=NULL)
        {
            A[k]=p->key;
            k++;
            p=p->next;
        }
    }
}

int main()
{
    int A[]={11,45,42,24,67,32,55};
    int len = sizeof(A)/sizeof(int);
    BucketSort(A,len);
    for(int i=0;i<len;i++)
    {
        printf("%d ",A[i]);
    }
    printf("
");
    return 0;
}