《第13周内排序第6讲-基数排序.pdf》由会员分享，可在线阅读，更多相关《第13周内排序第6讲-基数排序.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2 3 9 示例：示例： 百位百位十位十位个位个位 r=10 1、 基数基数排序的概念排序的概念 基数基数r：对于二进制数：对于二进制数r为为2，对于十进制数，对于十进制数r为为10。 记录记录Rj的的关键字关键字Rj.key kjd-1 kjd-2 kj1 kj0 d位数字或字符组成位数字或字符组成 每一位的值都在每一位的值都在0r- -1范围内，范围内， 其中其中r称为称为基数基数 一般地一般地 最 高 位 最 高 位 最 低 位 最 低 位 基数基数排序有两种：排序有两种：最低位优先（最低位优先（LSD）和和最高位优先（最高位优先（MSD）。 2、基数、基数排序的分类排序的分类 2 3
2、9 百位百位十位十位个位个位 最低位优先：从最低位优先：从个位个位 百位百位 最高位优先：从最高位优先：从百位百位 个位个位 选择哪种选择哪种基数排序，需要根据数据的特点来定。例如，对整基数排序，需要根据数据的特点来定。例如，对整 数序列递增排序，选择数序列递增排序，选择最低位优先，最低位优先，越重要的位越在后面排序。越重要的位越在后面排序。 最低位优先排序最低位优先排序过程过程如下：如下： 对对i = 0，1，d- -1，依次做一次依次做一次“分配分配”和和“收集收集”（使用使用r个队个队 列列Q0，Q1，Qr-1。 ） 。 分配：分配：开始时，开始时，把把Q0，Q1，Qr-1各个队列置成空
3、队列，然各个队列置成空队列，然 后依次考察线性表中的每一个节点后依次考察线性表中的每一个节点aj（j=0,1,n- -1），如果），如果aj 的关键字的关键字kji=k，就把，就把aj放进放进Qk队列中。队列中。 收集：收集：按按Q0，Q1，Qr-1顺序把各个顺序把各个队列中队列中的节点首尾的节点首尾相相 接，得到新的节点序列，从而组成新的线性表。接，得到新的节点序列，从而组成新的线性表。 由于数据需要放入队列，又要从队列由于数据需要放入队列，又要从队列取出来，需要大量元素移动。取出来，需要大量元素移动。 所以所以排序数据和队列均采用链表存储更好排序数据和队列均采用链表存储更好。 建立建立10
4、个队列，个队列，f为队头，为队头，r为队为队尾尾 进行进行第第1次次分配：按分配：按个位个位 进行进行第第1次次收集收集 p 369367 167 239 237 138 230 139 f0 r0 f7 r7 f8 r8 f9 r9369 367 167 237 239 139 138 230 p230 367 167 237 138 369 239 139 例如（例如（ 369,367,167,239,237,138,230,139），采用基数排序），采用基数排序 第第1趟排序完毕趟排序完毕 分配分配时是按一个一个元素进行的时是按一个一个元素进行的 收集收集时是按一个一个队列进行的时是按一
5、个一个队列进行的 进行进行第第2次次分配：按分配：按拾位拾位 进行进行第第2次次收集收集 f3 r3 f6 r6367 167369 230 p 第第2趟排序完毕趟排序完毕 237138139239 p230 367 167 237 138 369 239 139 230 237138139239367 167369 进行进行第第3次次分配：按分配：按百位百位 f1 r1 f2 r2 f3 r3 239 139138 237230 369367 p230 237138139239367 167369 167 进行进行第第3次次收集收集 p 第第3趟排序完毕趟排序完毕 1391381672392
6、37230369367 基数排序是通过“分配”和“收集”过程来实现基数排序是通过“分配”和“收集”过程来实现排序，排序，不不需需 要关键字的比较要关键字的比较。 结论结论 #define MAXE 20/线性表中最多元素个数线性表中最多元素个数 #define MAXR 10/基数的最大取值基数的最大取值 #define MAXD 8/关键字位数的最大取值关键字位数的最大取值 typedef struct node char dataMAXD;/记录的关键字定义的字符串记录的关键字定义的字符串 struct node *next; RecType1;/单链表中单链表中每个节点的每个节点的类型类
7、型 a1 p a2a3an 基数排序数据的存储结构基数排序数据的存储结构 3、 基数排序基数排序算法算法 void RadixSort(RecType1 * /定义各链队的首尾指针定义各链队的首尾指针 int i, j, k; for (i=0;id;i-)/从低位到高位做从低位到高位做d趟排序趟排序 for (j=0;jdatai-0;/找第找第k个链队个链队 if (headk=NULL)/进行分配进行分配,即采用尾插法建立单链表即采用尾插法建立单链表 headk=p; tailk=p; else tailk-next=p; tailk=p; p=p-next;/取下一个待排序取下一个待排
8、序的节点的节点 分配 p=NULL; for (j=0;jnext=headj; t=tailj; t-next=NULL;/最后一最后一个节点的个节点的next域置域置NULL 排序完成后，排序完成后，p指向的是一个有序指向的是一个有序单单链表。链表。 收集 注意：注意：C/C+将数值转换为字符串：将数值转换为字符串： 1 2 3 “3 2 1” 2 1 0 2 1 0 应该应该从从3 1，即低位到高位，即低位到高位 为了为了从从3 1，应该高位到低位，应该高位到低位 基数排序的基数排序的时间复杂度时间复杂度为为O(d(n+r) 其中：分配为其中：分配为O(n) 收集为收集为O(r)（r为“基数”）为“基数”） d为“分配为“分配-收集”的趟数收集”的趟数 4、基数、基数排序算法分析排序算法分析 基数排序的基数排序的空间复杂度空间复杂度为为O(r) 本讲完本讲完