算法导论 桶排序

#include <stdio.h> #include <stdlib.h> #include <float.h> typedef struct NodeType { double key; NodeType *next; NodeType *pre; }Node,*NodePtr; void insertSort(Node n[],int k) { if(n[k].next == NULL || n[k].next->next==NULL) return; Node *i,*j; for(j=n[k].next->next;j!=NULL;j=j->next) { i=j->pre; double x=j->key; while(i->pre != NULL && i->key>x) { i->next->key=i->key; i=i->pre; } i->next->key=x; } } void bucketSort(double a[],int len) { Node n[11]; int i; for(i=0;i<11;i++) { n[i].key=DBL_MIN; n[i].pre=NULL; n[i].next=NULL; } for(i=0;i<len;i++) { int j=(int)(a[i]*10); NodePtr node=(NodePtr)malloc(sizeof(Node)); node->key=a[i]; node->next=NULL; node->pre=NULL; Node *nnext; nnext=n[j].next; if(nnext != NULL) nnext->pre=node; n[j].next=node; node->next=nnext; node->pre=&n[j]; } for(i=0;i<11;i++) { insertSort(n,i); } for(i=0;i<11;i++) { Node *nn=n[i].next; while(nn != NULL) { printf("%f ",nn->key); nn=nn->next; } } printf("\n"); } void main() { double a[10]={0.72,0.17,0.39,0.26,0.78,0.94,0.21,0.12,0.23,0.68}; bucketSort(a,10); getchar(); }