【专题】常见几种排序法比较

常见几种排序方法复习冒泡法、选择法、插入法、桶排序、索引排序比较方向：从右往左比较，先确定左侧数组元素规则：从右往左先定左比较方向：从左往右比较，先确定数组元素a(i)规则：无论左右先定i总是拿a(i)右侧数据来比较k=jFori＝1Ton－1Forj＝1Ton-iIfa(j)>a(j+1)Thentemp＝a(j+1)a(j+1)＝a(j)a(j)＝tempEndIfNextjNexti比较方向：从左往右比较，先确定右侧数组元素规则：从左往右先定右冒泡法变式一：Fori＝nTo2step-1Forj＝1Toi-1Ifa(j)>a(j+1)Thentemp＝a(j+1)a(j+1)＝a(j)a(j)＝tempEndIfNextjNexti比较方向：从左往右比较，先确定右侧数组元素规则：从左往右先定右冒泡法变式二：Fori＝nTo2step-1Forj＝nTon-i+2step-1Ifa(j)>a(j-1)Thentemp＝a(j-1)a(j-1)＝a(j)a(j)＝tempEndIfNextjNexti比较方向：从右往左比较，先确定左侧数组元素规则：从右往左先定左冒泡法变式三：Fori＝1Ton—1k＝iForj＝nToi＋1

step-1

Ifa(j)＜a(k)Thenk＝jNextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti比较方向：从右往左比较，先确定数组元素a(i)规则：无论左右先定i选择法变式一：总是拿a(i)右侧数据来比较Fori＝nTo2step-1k＝iForj＝

1Toi-1

Ifa(j)＜a(k)Thenk＝jNextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti比较方向：从左往右比较，先确定数组元素a(i)规则：无论左右先定i选择法变式二：总是拿a(i)左侧数据来比较Fori＝nTo2step-1k＝iForj＝

i-1To1

step-1Ifa(j)＜a(k)Thenk＝jNextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti比较方向：从右往左比较，先确定数组元素a(i)规则：无论左右先定i选择法变式三：总是拿a(i)左侧数据来比较核心问题：无论哪一种排序，每一轮(遍)排序，都是将最大或最小的放在数组剩余元素最左侧或最右侧，应当确保接下来每一轮(遍)比较是对所有剩余数组元素的比较，不能有遗漏。某VB程序段如下：Fori=1To3

Forj=i+1To6

Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti数组元素a(1)到a(6)的值依次为“99，100，30，21，43，19”，经过该程序段“加工”后a(4)、a(5)、a(6)的值依次为__________________解析：此例并不是冒泡法排序，标准的冒泡法排序，从左往右比较，每次都应当是从最左边固定元素往右（如FORi=1to……），右侧参与比较的数据每一遍减少一个，反之，从右往左比较，每次都应当是从最右边固定元素往左（如FORi=nto……），左侧参与比较的数据每一遍减少一个此例当i=1时，第一遍比较，99与100比较，不用交换，然后100与后面的每一个都交换，数组值变为：99，30，21，43，19，100，第二遍，99不再参加比较，30与21交换，43与19交换，变为：99，21，30，19，43，100，第三遍，99，21不再参加比较，30与19交换，变为：99，21，19，30，43，100，所以答案为：30，43，100插入法排序核心代码（升序为例）Fori=2To10

tmp=a(i)j=i-1DoWhiletmp<a(j)a(j+1)=a(j)j=j-1Loopa(j+1)=tmpNexti插入排序变形(升序）升序为例fori=2ton

tmp=a(i)

j=1

dowhiletmp>=a(j)

j=j+1

ifj=ithenexitdo

loop

fork=itoj+1step-1

a(k)=a(k-1)

nextk

a(k)=tmpnexti桶排序的算法思想最快最简单的排序：桶排序期末考试完了老师要将同学们的分数按照从高到低排序。班上只有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.验证数据是否存在。桶排序桶排序 桶排序的算法思想是：如图a所示，有10个桶，编号为1～10。每出现一个数，就在对应编号的桶中的放一面小旗子，最后只要看每个桶中有几面小旗子就可以了。例如2号桶中有1面小旗子，表示2出现了一次；3号桶中有1面小旗子，表示3出现了一次；5号桶中有2面小旗子，表示5出现了两次；8号桶中有1面小旗子，表示8出现了一次。最后只要按桶的编号顺序逐次输出非空的桶编号即可实现排序功能。桶排序桶排序小明利用桶排序的算法思想实现对5个[1，10]随机整数的排序过程。实现上述功能的VB程序如图b所示，请在划线处填入合适的代码。Dima(1To5)AsInteger

′数组a用于存放数字Dimb(1To10)AsInteger

′数组b相当于桶PrivateSubForm_Load()

′生成5个[1，10]随机整数

List1.Clear

Randomize

Fori＝1To5桶排序b(a(i))＝b(a(i))＋1桶排序b(i)Str(i)桶排序解析：本题考查VB基本程序阅读及运算能力。①该程序使用了桶排序的算法思想，数组b相当于桶，用于记录数组a的小旗子的数量，也就是说数组a的值是数组b的下标，数组b的值是数组a的值出现的次数，因此答案是b(a(i))＝b(a(i))＋1。请特别注意，该题涉及数组嵌套，即数组a的值是数组b的下标。②如果小旗子的数量多于1面，则需要输出多次，因此内循环是控制输出次数的，其终值由b(i)决定，当b(i)＝0时，相当于不输出。③排序后输出数据，只需要输出桶的编号i并将其转换为字符类型即可。索引排序索引排序是指不改变原始数组a()数据的前提下，引用新的数组b()用于记录a()数组元素在所有元素中的排名（即索引），简单说就是通过排序交换数组b()元素的值，比如升序排列，b(1)就要记录下a()数组中值最小的元素的下标，b(2)就要记录下a()数组中值第二小的元素的下标，依此类推。下标原始原始下标排序排序后i=1b(1)=1a(1)=9a(b(1))=9i=1b(1)=4a(b(1))=3a(4)=3i=2b(2)=2a(2)=6a(b(2))=6i=2b(2)=5a(b(2))=4a(5)=4i=3b(3)=3a(3)=8a(b(3))=8i=3b(3)=2a(b(3))=6a(2)=6i=4b(4)=4a(4)=3a(b(4))=3i=4b(4)=3a(b(4))=8a(3)=8i=5b(5)=5a(5)=4a(b(5))=4i=5b(5)=1a(b(5))=9a(1)=9索引排序之结合选择法排序Dima(1To5)AsInteger，b(1To5)AsIntegera(1)=9:a(2)=6:a(3)=8:a(4)=3:a(5)=4Fori=1To5'初始化b(i)=iNextiFori=1To4k=iForj=i+1To5Ifa(b(k))>a(b(j))Thenk=jNextjIfk<>iThent=b(k):b(k)=b(i):b(i)=tNextiFori=1To5List1.AddItemStr(a(b(i)))Nexti索引排序之结合冒泡法排序Dima(1To5)AsInteger，b(1To5)AsIntegera(1)=9:a(2)