线上第17节桶排序

作业讲解看录播桶排序桶排序的算法思想排序的算法有很多，我们已经学了冒泡排序及其优化，选择排序，还有其他的桶排序、插入排序、希尔排序、快排序等等，感兴趣的同学可以去网上搜索我们上课没讲过的排序方法。今天要讲解的一种排序方法就是：最快最简单的排序：桶排序如下图所示，桶排序的算法思想是这样的：如要对[1,10]范围内的5，3，5，2，8这几个数进行排序，可以通过这样的方法来实现，假设有10个桶，从1～10对桶进行编号。每出现一个数，就在对应编号的桶中放一面小旗子，最后只要数数每个桶中有几面小旗子就可以了。例如2号桶中有1面小旗子，表示2出现了一次；3号桶中有1面小旗子，表示3出现了一次；5号桶中有2面小旗子，表示5出现了两次；8号桶中有1面小旗子，表示8出现了一次。桶排序思维：首先明确A数组中的数值范围，然后新建一个数组B，下标范围就是A数组中数值范围。将A数组中的数放入B数组与之下标对应的桶中，然后按照桶的编号输出，即可完成排序。如a数组中的数字数值范围在1到10，则可以定义一个b数组，下标范围为[1,10],即dimb(1to10)asinteger若a数组中的数据如图所示，因a(1)=5,把a(1)放入5号桶b(5)中，b数组元素用来计数，即b(5)=b(5)+1b(a(1))=b(a1)+1A(1)A(2)A(3)A(4)A(5)53528具体实施在输出时，如果是升序排序，只要按照桶的编号，从小到大对桶进行检查，如果发现桶里面只要有1面以上的小旗子(非空)就输出桶的编号，如果有2面小旗子就连续输出两次，依次类推┈┈，这样就快速地实现了升序排列。而如果是在排序时去除重复的数据，则更加简单了。一般来说，桶的算法思想主要有以下三种功能：1.桶计数功能、2.桶排序功能、3.验证数据是否存在。b(a(i))=b(a(i))+1Dima(1To5)AsInteger′数组a用于存Dimb(1To10)AsInteger′数组b相当于桶PrivateSubForm_Load()′生成5个[1，10]随机整数List1.ClearRandomizeFori＝1To5a(i)＝Int(Rnd*10)＋1List1.AddItemStr(a(i))NextIEndSubPrivateSubCommand1_Click()′桶排序(升序)算法实现List2.ClearFori＝1To5①______________________NextIFori＝1To10Forj＝1To②List2.AddItem③NextjNextiEndSub小明利用桶排序的算法思想实现对5个[1，10]随机整数的排序过程。实现上述功能的VB程序如图b所示，请在划线处填入合适的代码。b(a(i))＝b(a(i))＋1b(i)Str(i)程序实现图a图b解析：本题考查VB基本程序阅读及运算能力。①该程序使用了桶排序的算法思想，数组b相当于桶，用于记录数组a的小旗子的数量，也就是说数组a的值是数组b的下标，因此答案是b(a(i))＝b(a(i))＋1。请特别注意，该题涉及数组嵌套，即数组a的值是数组b的下标。②如果小旗子的数量多于1面，则需要打印多次，因此内循环是控制打印次数的，其终值由b(i)决定，当b(i)＝0时，相当于不打印。③排序后输出数据，只需要输出桶的编号i并将其转换为字符类型即可。例2：有如下VB程序段：n＝0Fori＝1ToLen(Text1.Text)c＝Mid(Text1.Text,i,1)Ifc＝“0”Andc＝“9”Thenm＝1Elsem＝2Endifa(m)＝a(m)＋1Ifa(m)＝1Thenn＝n＋1Nexti数组a各元素的初始值都为0，文本框Text1的内容为“Happy2017”。执行该程序段后，变量n的值为()A．1B．2C．4D．9B解析：本题考查VB基本程序阅读及运算能力。由程序可知，该算法使用了桶排序的思想。数据元素a(1)用于存储数字字符的个数，数据元素a(2)用于存储非数字字符的个数。当遇到第1个数字或非数字时，a(1)＝1时和a(2)＝1时，执行n＝n＋1。因此最终n的值为2，所以本题答案是B。桶排序特点小结1,桶排序是稳定的2,桶排序是常见排序里最快的一种3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法桶排序:最快最简单的排序缺点:最占内存(适用于数据比较集中的排序）一般来说，桶的算法思想主要有以下三种功能：1.桶计数功能、2.桶排序功能、3.验证数据是否存在。作业：Word文档+天学网