海口网站建设电话,江苏工程信息网,做网站网页维护手机App开发,建设部领导干部官方网站基数排序
基本思想
基数排序其实就是依靠多位关键字进行排序#xff0c;现在我们有一个数据为101#xff0c;那么“101”就是一个三位
关键字#xff0c;分别为#xff1a;“百位-1”、“十位-0”、“个位-1”。
此时我们就可以按照三位关键字进行排序现在我们有一个数据为101那么“101”就是一个三位
关键字分别为“百位-1”、“十位-0”、“个位-1”。
此时我们就可以按照三位关键字进行排序一般而言排序有两种“最高位优先MSD”、“最
低位优先LSD”。
名词概念
基数
还是对于上面的数据101它是一个三位关键字分别为“1”、“0”、“1”对于每一位关键字它
的取值范围为“0-9”共十种可能我们把这些可能性称为“基数”简写为r因此可以说
101基数为10r10。
关键字位数
仍然对于数据101来说共有三位因此它的关键字位数就是三位分别为“百位”、“十位”、“个
位”。
代码思路
基数排序的精髓在于“分配”、“收集”。
每次按关键字进行分配当前趟数的关键字相同的数据分配到一个队列中。
每次分配完毕后都需要将不同队列的数据连接在一起形成一个新的链表。
我们需要使用链式结构来存储数据同时创建r基数个队列用来辅助存储我们交换中的数
据。
代码实现
#includestdio.h
#includemath.h
#define MAX_KEY 8 //关键字最大位数
#define RADIX 10 //关键字基数
#define MAX_SPACE 100 //数据单元大小
typedef struct{int keys; //关键字 int next; //下一个数据位置
}SLnode; //静态链表单元
typedef struct{SLnode R[MAX_SPACE1]; //R[0]做哨兵单元 int length; //静态链表中数据长度 int keynum; //关键字位数
}SLList;
typedef int Queue[RADIX]; //静态队列void InitMySLList(SLList *L)
{int Sample_Data[10] {614,738,921,485,637,101,215,530,790,306};int i;L-length 10; //链表长度 L-keynum 3; //关键字位数for(i1;iL-length;i){L-R[i].keys Sample_Data[i-1]; //初始化数据 }for(i0;iL-length;i){L-R[i].next i 1; //修改next域,组建成一个静态链表. } L-R[L-length].next 0; //尾结点指向0
}int GetKey(int n,int i) //求第i位关键字,n为数据
{int k;k ((int)(n / pow(RADIX,i))) % RADIX;return k;
}void Distribute(SLList *L,int i,Queue f,Queue e) //第i趟分配函数
{//静态链表中的0-i-1位关键字已经有序//队列中存储的是数据在静态链表中的位置(索引)//实现按第i位关键字有序建立RADIX个队列.//f,e分别代表队头指针和队尾指针int j,p;for(j0;jRADIX;j){ //初始化队列 f[j] 0;e[j] 0;}for(pL-R[0].next;p;pL-R[p].next){j GetKey(L-R[p].keys,i); //求第i位关键字 if(f[j] 0) //队列为空时,直接从队头入第一个数据 f[j] p;else //队列不为空,需要从队尾入数据,也就是队列中最后一个元素的next域 L-R[e[j]].next p;e[j] p; //队尾指针存储队列中的最后一个数据. }
}void Collections(SLList *L,int i,Queue f,Queue e) //第i趟收集
{int j,t;for(j0;f[j]0;j); //找到第一个非空队列L-R[0].next f[j]; //R[0].next 指向第一个非空队列队头t e[j]; //t指向第一个非空队列队尾while(jRADIX){for(j;jRADIX-1!f[j];j);if(f[j] jRADIX){ //jRADIX不能漏 L-R[t].next f[j]; //当前队尾和下一个队头相连接 t e[j]; //t存储最新队列的队尾 }}L-R[t].next 0; //队尾指向0
}void RaDixSort(SLList *L) //基数排序
{Queue f,e;int i;for(i0;iL-keynum;i){Distribute(L,i,f,e);Collections(L,i,f,e);}
}void OutPutMyRadix(SLList *L) //打印结果
{int i;for(iL-R[0].next;i;iL-R[i].next){printf(%d ,L-R[i].keys);}
} int main()
{SLList L;InitMySLList(L);RaDixSort(L);OutPutMyRadix(L);return 0;
}
