常见几种排序法比较—【教学课件】.pptx

常见几种排序法比较—【教学课件】常见几种排序方法复习比较方向：从右往左比较先确定左侧数组元素规则：从右往左先定左Fori＝1Ton－1Forj＝1Ton-iIfa(j)>a(j+1)Thentemp＝a(j+1)a(j+1)＝a(j)a(j)＝tempEndIfNextjNextiFori＝nTo2step-1Forj＝1Toi-1Ifa(j)>a(j+1)Thentemp＝a(j+1)a(j+1)＝a(j)a(j)＝tempEndIfNextjNextiFori＝nTo2step-1Forj＝nTon-i+2step-1Ifa(j)>a(j-1)Thentemp＝a(j-1)a(j-1)＝a(j)a(j)＝tempEndIfNextjNextiFori＝1Ton—1k＝iForj＝nToi＋1step-1Ifa(j)＜a(k)Thenk＝jNextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNextiFori＝nTo2step-1k＝iForj＝1Toi-1Ifa(j)＜a(k)Thenk＝jNextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNextiFori＝nTo2step-1k＝iForj＝i-1To1step-1Ifa(j)＜a(k)Thenk＝jNextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti核心问题：无论哪一种排序每一轮(遍)排序都是将最大或最小的放在数组剩余元素最左侧或最右侧应当确保接下来每一轮(遍)比较是对所有剩余数组元素的比较不能有遗漏。某VB程序段如下：Fori=1To3Forj=i+1To6Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti数组元素a(1)到a(6)的值依次为“9910030214319”经过该程序段“加工”后a(4)、a(5)、a(6)的值依次为__________________插入法排序插入排序变形(升序）桶排序的算法思想最快最简单的排序：桶排序期末考试完了老师要将同学们的分数按照从高到低排序。班上只有5个同学这5个同学分别考了5分、3分、5分、2分和8分考得真是惨不忍睹(满分是10分)。接下来将分数进行从大到小排序排序后是85532。那么有没有什么好方法编写一段程序让计算机随机读入5个数然后将这5个数从大到小输出。如下图所示桶排序的算法思想是这样的：要对分数进行排序可以通过这样的方法来实现假设有11个桶从0～10对桶进行编号。每出现一个数就在对应编号的桶中放一面小旗子最后只要数数每个桶中有几面小旗子就可以了。例如2号桶中有1面小旗子表示2出现了一次；3号桶中有1面小旗子表示3出现了一次；5号桶中有2面小旗子表示5出现了两次；8号桶中有1面小旗子表示8出现了一次。在输出时如果是升序排序只要按照桶的编号从小到大对桶进行检查如果发现桶里面只要有1面以上的小旗子(非空)就输出桶的编号如果有2面小旗子就连续输出两次依次类推┈┈这样就快速地实现了升序排列。而如果是在排序时去除重复的数据则更加简单了。一般来说桶的算法思想主要有以下三种功能：1.桶计数功能、2.桶排序功能、3.验证数据是否存在。桶排序桶排序桶排序桶排序桶排序桶排序索引排序索引排序之结合选择法排序索引排序之结合冒泡法排序