4.2《基数排序》

4.2基数排序 高中信息技术/教科版/选择性必修1 目录 1.游戏导入 2.分析与抽象 3.编程实现 4.课堂小结 1.游戏导入 第一步：将A4纸对折5次 第二步：将其中10张10张小卡片写上0，1，2，3，4，5，6，7，8，9，从左到右依次摆在自己面前。这10个数字叫“队伍编号”。 0 1 2 3 4 5 6 7 8 9 第二步：将其中10张10张小卡片写上0，1，2，3，4，5，6，7，8，9，从左到右依次摆在自己面前。这10个数字叫“队伍编号”。 0 1 2 3 4 5 6 7 8 9 队伍编号 第三步：在剩下的每张卡片上随意写一些对你来说有意义的数字，数字的大小小于10000，不必把剩下的卡片全部用完，用 10 张以上就可以。 129 9 182 501 493 213 45 732 314 46 697 6 81 316 35 第四步：洗卡片，确保这些数字杂乱无序。把卡片数字朝下放成一摞，在后面的操作中，写有数字的卡片都是数字朝下放。 129 9 182 501 493 213 45 732 314 46 697 6 81 316 35 第五步：现在从手里写着有意义数字的卡片中从下到上依次取出卡片，按卡片上数字的个位把数字分到相应队伍编号的下方位置。分发完成后，按队伍编号从小到大，依次把各队伍的一摞卡片收集到一起，卡片数字朝下，队伍编号数字大的放在上面。 0 1 2 3 4 5 6 7 8 9 队伍编号 个位 501 81 182 732 493 213 314 45 35 46 316 6 697 129 9 第六步：重复第五步，依次按十位数、百位数、千位数分发和收集卡片。 第七步：最后把收集到的卡片翻过来，从左到右依次摆在桌面上，看一看有什么神奇的效果。 2.分析与抽象 任务一体验手动基数排序 活动1热身运动:拆分数位 请拆分3999，28，109的数位，并将结果填写在表 4.2.1中。 数 千位 百位 十位 个位 3999 3 9 9 9 28 109 表4.2.1 拆分数位 填一填 0 0 2 8 0 1 0 9 任务一体验手动基数排序 活动1热身运动:拆分数位 十进制记数是逢十进一，从零开始计数，数到十的时候，就要进一位，即变成 10，个位数上是 0，十位数上是 1。一个十进制数的每个数位上可能的数字是 0，1，2，···，9 中的某一个。十进制的基数是10。二进制记数是逢二进一，从零开始计数，数到二的时候，就要进一位，即变成10(2)。一个二进制数的每个数位上可能的数字是0，1。二进制的基数是2。 同理，一个 N 进制数是逢 N 进一，它的基数是N，采用N个不同的数字符号来表示。例如，十六进制的基数是16，采用0~9和A~F这16个符号来记数。 基数 任务一体验手动基数排序 活动2自制数字纸牌接龙游戏 课间，小明跟同桌玩起了自制数字纸牌接龙游戏。他手中拿着15张纸牌，每张纸牌上有一个数，如图 4.2.1所示。 图4.2.1 自制数字纸牌 这个游戏的操作主要是纸牌的分发和收集，小明用这副纸牌演示游戏的玩法如下。 任务一体验手动基数排序 活动2自制数字纸牌接龙游戏 第1次接龙 第1步：将如图4.2.1所示的纸牌从左到右依次抽出，以纸牌的个位数为准进行分发，个位数相同的纸牌放在同一列上，即个位数为0的放在第1列，个位数为1的放在第2列，以此类推。当纸牌的个位数相同的时候.先抽出的纸牌放在前面，后抽出的纸牌放在后面。结果如图4.2.2所示。 图4.2.2依据个位数分发的结果 任务一体验手动基数排序 活动2自制数字纸牌接龙游戏 第2步:将纸牌按图 4.2.2中箭头所示的顺序从左到右从上到下收集，结果如图 4.2.3所示。 图4.2.3 第1次收集后纸牌的顺序 第2次接龙 第1步:将如图4.2.3所示的纸牌从左到右依次抽出，以纸牌的十位数为准分发，十位数相同的纸牌排在同一列上，结果如图所示。 任务一体验手动基数排序 活动2自制数字纸牌接龙游戏 第 2步:将纸牌按图4.2.4中箭头所示的顺序收集，结果如图4.2.5所示。 图4.2.5第2次收集后纸牌的顺序 第3次接龙 第1步:将如图4.2.5所示的纸牌从左到右依次抽出，以纸牌的百位数为准分发，百位数相同的纸牌排在同一列上。 图 4.2.6中已经将前5 张纸牌按百位数分发，请将后面的 10 张纸牌按百位数分发，把结果填写在图 4.2.6 中并标出表示收集顺序的箭头。 任务一体验手动基数排序 活动2自制数字纸牌接龙游戏 图4.2.6 依据百位数分发的结果 221 336 378 582 845 28 32 28 62 91 任务一体验手动基数排序 活动2自制数字纸牌接龙游戏 第2步:将纸牌按从左到右、从上到下的顺序收集，把图4.2.7补充完整。 图4.2.7第3次收集后纸牌的顺序 经过3次接龙，纸牌按照其上面数的大小，从小到大排成了一排。 32 62 91 109 115 221 336 378 582 668 845 思考：如果数字的最大位数有5位，会经过多少轮接龙才能实现排序呢? 基数排序(radix sort) 通过多轮分发和收集来完成排序。从个位开始，由低位到高位依次分发和收集。 每一次分发，以指定数位为准，把正整数分发到不同的基数队列中。收集时，按基数队列序号从小到大依次把正整数收集到一个队列中当对所有数位进行分发和收集后，排序就完成了。 基数排序 任务一体验手动基数排序 活动2自制数字纸牌接龙游戏 3.编程实现 任务二 编程实现基数排序 活动1建立数据结构 编写函数radixSort(alist)实现基数排序。mainQueue最开始保存用户要排序的数据，可以通过循环让列表alist中的待排序数据依次进入队列。 01.#基数排序主程序 02. def radixSort(alist): 03.mainQueue=Queue() #建立mainQueue队列 04.radixQueues=[Queue() for i in range(10)] #建立基数队 05.for a in alist: #数据放入mainQueue队列 06.mainQueue.enQueue(a) 任务二 编程实现基数排序 活动2设计算法 基数排序的算法描述如下。 (1)循环步骤(2)(3)共k轮 (2)把队列mainQueue中的数据分发到radixQueues的各个队列中。 (3)把radixQueues各个队列中的数据收集到队列mainQueue中根据以上算法， 补全下面的代码。 07.k=len(str(max(alist))) #最大数的位数 08.for i in range(1, k+1): #分发和收集k轮 09.distribute(mainQueue，radixQueues，i) #分发 10.gather(mainQueue，radixQueues) #收集 任务二 编程实现基数排序 活动2设计算法 11.alist.clear() #清空alist 12.#把队列mainQueue中的数据放入列表 13.while not . 14.alist.append(mainQueue.deQueue()) 在以上代码中，k=len(str(max(alist)))用于求列表中的最大数的位数。 mainQueue.isEmpty( ): 任务二 编程实现基数排序 活动2设计算法 接下来，对算法中调用的两个函数 distribute和gather 进一步细化，确定其算法。 函数 distribute 的功能是把 mainOueue 中的数据分发到基数队列radixQueues中，分发时以第i数位上的数字为准。这个函数依次取出队列 mainQueue中的每个数据a，取出第i数位上的数字m，把a分发到radixQueues的第m个队列中，放在队列的最后面。怎样取得一个数a的第i位(i从1开始) 呢? 以a=1234为例: 任务二 编程实现基数排序 活动2设计算法 (1)取得第1位:a%10//1 (2)取得第2位:a%100//10 (3)取得第3位:a%1000//100 (4)取得第4位:a%10000//1000 可以看到，可以通过表达式得到第i数位上的基数: a%(10**i)//(10**(i-1)) 任务二 编程实现基数排序 活动2设计算法 mainQueue中的数据依次出队，然后根据基数入队到相应的队列中函数distribute的算法描述如下 (1)从队列mainQueue中依次取出数据a。 (2)如果是第i轮分发，则取出数据a的第i数位上的数字m。 (3)把数据a入队到队列radixQueues[m]中。 以上算法可以通过下面的代码来实现。 15.#把mainQueue中的数据按第i位分发到队列radixQueues中 16. def distribute(mainQueue,radixQueues,i): 17.while not mainQueue.isEmpty(): 任务二 编程实现基数排序 活动2设计算法 18.a=mainQueue.deQueue() 19.m=a%(10**i)//(1**(i-1)) #取出第i位上的数字 20.radixQueues[m].enQueue(a) 函数gather的功能是收集 radixQueues 中各队列数据到mainQueue中，其算法描述如下。 (1) 按序号从小到大收集radixQueues 中各队列的数据。 (2)各个队列中的全部数据依次出队，然后将它们加入队列mainOueue中。 代码如下。 任务二 编程实现基数排序 活动2设计算法 21.#把列表radixQueues中的数据收集到队列mainQueue中 22. def gather(mainQueue,radixQueues): 23.for q in radixQueues: 24.while not q.isEmpty( ): 25.a=q.deQueue() 26.mainQueue.enQueue(a) 任务二 编程实现基数排序 活动3编程实现 活动2已经完成了基数排序的算法设计和代码实现，请将活动2的代码集中输入到一个程序文件中，用以下数据对程序进行测试: 27.alist=[109,378,28,5,10,7,21,845,62,582,91,336,2,68,32] 28.radixSort(alist) 29.print(alist) 4.课堂小结 分发过程 分发的过程是按照数据的某个数位上的数字依次把队列 mainQueue中的各个数据分发到相应的基数队列中，最先入队的数据处于队列的队首位置。 收集过程 收集的过程是按照基数队列下标从小到大的顺序，将所有基数队列中的数据移出队列，放入队列 mainQueue，最先入队的数据处于队列的队首位置。 迭代次数 k是需要排序的所有数据中最大值的位数，它可以通过以下表达式得到: k=len(str(max(alist))) 基数排序的基本思路 下节课见！ $$