首页 > 代码库 > 基数排序 - 主位优先
基数排序 - 主位优先
算法思想：
主位优先 排序好后直接导出
2,130,22,10,1230,4565,64,340,2430,1340
D=4。
桶0:2,130,22,10,64,340, || 桶1:1230,1340 || 桶4:4565
D=3
桶0：2，22,10,64 桶1:130 桶3：340 || 桶2:1230 桶3 1340 || 桶5：4565
D=2
桶0:2 桶1：10 桶2:22 桶6：64 || 桶3:130 || 桶4:340 || 桶3:1230 || 桶4:1240 || 桶6： 4565
D=1
桶2:2 || 桶0:10 ||桶2:22 ||桶4:64 ............................................................................
1 void MSD( ElementType A[], int L, int R, int D ) 2 { 3 Bucket B; 4 int i,j ,Di; 5 PtrToNode P,temp,list=NULL; 6 7 8 if(D==0) return; 9 /*初始化桶*/10 for(i=0;i<Radix;i++)11 12 B[i].head=B[i].tail=NULL;13 14 /*将数组逆序导入链表list*/15 for(i=L;i<=R;i++)16 {17 temp=(PtrToNode)malloc(sizeof( struct Node)); //新建temp18 temp->key=A[i]; 19 temp->Next=list; // 第一次temp为list list为null20 list=temp; //更新list 为temp21 }22 23 /*分配*/24 P=list;25 while(P)26 {27 Di=GetDigital(P->key,D);28 temp=P;29 P=P->Next;30 if (B[Di].head == NULL) B[Di].tail = temp;31 temp->Next = B[Di].head;32 B[Di].head = temp;33 34 }35 /*收集*/36 37 i=j=L;38 for(Di=0;Di<Radix;Di++)39 {40 if(B[Di].head)41 {42 P=B[Di].head;43 while(P)44 {45 temp=P;46 P=P->Next;47 A[j++]=temp->key;48 free(temp);49 }50 MSD(A,i,j-1,D-1); 51 i=j;52 }53 }54 }55 void MSDRadixSort( ElementType A[], int N )56 { /* 统一接口 */57 MSD(A, 0, N-1, MaxDigit); 58 }
错误分析:
1 42行 注意不要将list赋给p
2 30行不好理解
...............................................
基数排序 - 主位优先