排序算法及程序实现课件2.pptx

1、排序算法及程序实现（2）2教材研读一排序算法的基本思想二排序算法的程序实现3重难突破突破一 冒泡排序的变形4教材研读知识梳理一、排序算法的基本思想通常被排序的数据是一批同类型数据,存储在具有适当规模的数组变量中。通过排序可以调整数据在数组变量中的存储位置,使数组内的数据呈现某种次序。5知识梳理(1)选择排序选择排序的基本思想是在所有的记录中选出最小(大)的数据,把它与第一个数据交换,然后在其余的记录中再选出最小(大)的数据与第二个数据交换。以此类推,直至所有数据排序完成。n 个数需要n-1 次加工(挑选最小或最大数然后进行交换)。6知识梳理以数据130,20,98,15,67,3 为例,从小到

2、大选择排序的过程如下:7原始数据130209815673第1遍排序后320981567130第2遍排序后315982067130第3遍排序后315209867130第4遍排序后315206798130第5遍排序后315206798130知识梳理(2)选择排序的代码如下:For i=1 To n-1k=iFor j=i+1 To nIf a(j)a(k)Then k=j Next j8知识梳理If ki Thentemp=a(i):a(i)=a(k):a(k)=tempEnd IfNext i9知识梳理说明:虚线框内代码用于寻找数组元素a(i)到a(n)的最小值,变量k记录当前找到的最小值的位置

3、,即数组元素的下标,则a(k)就是当前找到的最小的数组元素。它的思想方法是先假设数组的第i项是最小的(第i遍排序),因此k记为i,然后把从第i+1项开始的所有数组元素跟a(k)进行比较,如果比a(k)小,则用k记录该元素的下标。这样循环结束后,变量k中存储的就是数组中从第i项至第n项的最小元素的下标,a(k)就是第i项至第n项中的最小元素。从小到大排序时,If语句中条件表达式为:a(j)a(k)。10自我检测1.按日期先后整理一堆文件的算法是:第一次,在这叠文件中从上到下找出日期最早的文件反扣在桌面上;第二次从剩余文件中从上到下找出日期最早的文件反扣在第一次找出的文件上;第三次,从剩余文件中从

4、上到下找出日期最早的文件反扣在第二次找出的文件上;,依此类推,最后完成整理工作。此算法属于()A.选择排序B.对分查找C.递归算法D.冒泡排序11自我检测1.按日期先后整理一堆文件的算法是:第一次,在这叠文件中从上到下找出日期最早的文件反扣在桌面上;第二次从剩余文件中从上到下找出日期最早的文件反扣在第一次找出的文件上;第三次,从剩余文件中从上到下找出日期最早的文件反扣在第二次找出的文件上;,依此类推,最后完成整理工作。此算法属于(A)A.选择排序B.对分查找C.递归算法D.冒泡排序12自我检测解析本题主要考查选择排序的基本思想。选择排序的基本思想是从所有的记录中选出最大或最小的数据,把它与第一

5、个数据交换,然后在其余的记录中再选出最大或最小的数据与第二个数据交换。以此类推,直至所有数据排序完成。本题中解决问题的思想方法是选择排序的基本思想。13自我检测2.用选择排序法对一组学生的身高数据进行升序排序,已知第一遍排序结束后的数据序列为165,168,178,175,171,则下列选项中可能是原始数据序列的是()A.175,178,168,165,171B.178,168,165,175,171C.165,178,168,175,171D.165,168,171,175,17814自我检测2.用选择排序法对一组学生的身高数据进行升序排序,已知第一遍排序结束后的数据序列为165,168,1

6、78,175,171,则下列选项中可能是原始数据序列的是(B)A.175,178,168,165,171B.178,168,165,175,171C.165,178,168,175,171D.165,168,171,175,17815自我检测解析本题主要考查选择排序的基本思想。选择排序的基本思想是从所有的元素中选出最小(升序排序)的数据,把它与第一个数据交换,然后在其余的元素中再选出最小的数据与第二个数据交换。以此类推,直至所有数据排序完成。因此第一遍排序后排第一位的165有5种可能的来源,原来就在第一位,不需要数据互换,那么原始数据就是165,168,178,175,171;从第二位换来,那

7、么原始数据就是168,165,178,175,171;从第三位换来,那么原始数据就是178,168,165,175,171;从第四位换来,那么原始数据就是175,168,178,165,171;从第五位换来,那么原始数据就是171,168,178,175,165。1617重难突破突破选择排序的变形1.选择排序的变形:For i=1 To n-1k=iFor j=n To i+1 step-1If a(j)a(k)Then k=jNext j18突破选择排序的变形If ki Then temp=a(i):a(i)=a(k):a(k)=tempEnd IfNext i在每一遍找最小值时,从前往后的

8、比较改为从后往前的比较,其他没有变化。19突破选择排序的变形2.选择排序的错误变形:For i=1 To n-1k=iFor j=i+1 To nIf a(j)a(i)Then k=jNext jIf ki Then temp=a(i):a(i)=a(k):a(k)=tempEnd IfNext i20突破选择排序的变形错误原因分析:在选择最小值的过程中把第i+1到第n个数依次与a(i)比较,“If a(j)a(i)Then k=j”,如果a(j)比a(i)小,则用变量k记录j的位置,但是a(j)与a(i)并未交换。这种方法是找不到最小值的位置的。比如有如下数据:5 2 1 3 4,第一遍排序

9、i=1时比较过程如下:a(2)a(1),因此k=2;a(3)a(1),因此k=1;a(4)a(1),因此k=4;a(5)a(1),因此k=5。这一趟循环的结果是k=5,没有找到最小值所在的位置(最小值位置应该是3),原因就是a(1)的值没有变过。21突破选择排序的变形3.选择排序的优化在数组的所有元素中同时找出最小和最大的元素,然后将这两个元素分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元素的数据按升序排列。代码如下:p=1:q=10Do While pqiMin=p:iMax=p22突破选择排序的变形Fo

10、r i=p+1 To qIf a(i)a(iMax)Then iMax=iNext it=a(iMin):a(iMin)=a(p):a(p)=tIf iMax=p Then iMax=iMint=a(iMax):a(iMax)=a(q):a(q)=tp=p+1q=q-1Loop23突破选择排序的变形思想解析:普通的选择排序是从头到尾一个方向的,优化后的排序是从两端往中间同时进行的,一端从小到大排,一端从大到小排,变量p和q表示本次排序的范围(p前和q后的数据已经完成排序)。FOR语句找出本次排序的最小数a(iMin)和最大数a(iMax),然后将a(iMin)与a(p)交换,将 a(iMax)

11、与a(q)交换。由于找最小数和最大数时,一开始都假定了p位置上的数是最小值和最大值,如果本次找到的最大值在p位置,那么当a(p)和a(iMin)交换以后,最大值a(p)就被换到iMin的位置。因此当iMax=p时,在最小值交换完毕后,再给iMax赋值iMin。24典型例题例3有如下VB程序段:a(l)=44:a(2)=36:a(3)=58:a(4)=65:a(5)=12b=0c=0For i=1 To 4k=iFor j=i+1 To 5If a(j)a(k)Then k=j:b=b+125典型例题Next jIf k i Thent=a(i):a(i)=a(k):a(k)=tc=c+1End

12、 IfNext iText1.Text=Str(b)+Str(c)该程序段执行后,文本框Text 1显示的内容是()A.53B.44C.43D.3426典型例题Next jIf k i Thent=a(i):a(i)=a(k):a(k)=tc=c+1End IfNext iText1.Text=Str(b)+Str(c)该程序段执行后,文本框Text 1显示的内容是(C)A.53B.44C.43D.3427典型例题解析本题首先要理解变量 b和变量 c的含义。变量 b 表示每趟排序后面(j)位置上的值有几个数比 k初始位置的值要小,变量 c 表示使用选择排序完成数据升序需要几次数据交换。第一趟排

13、序 k=1,初始位置的值为 44,后面有 2 个数比 44 小,找到最小数后与 44 交换一次。第二趟排序 k=2,初始位置的值为 36,后面没有数比 36 小,所以数据不交换。第三趟排序 k=3,初始位置的值为 58,后面有 1 个数比 58 小,找到并与之交换。第四趟排序 k=4,初始位置的值为 65,后面的数比 65 小,所以交换。b=4,c=3。所以答案选C。28典型例题例4某排序算法的VB程序段如下:For i=1 To 4k=iFor j=5 To i+1 Step-1If a(j)a(k)Then k=jNext jIf k i Thentmp=a(k):a(k)=a(i):a(

14、i)=tmp29典型例题f(i)=TrueEnd IfNext i当数组元素a(1)到a(5)的值依次为“8,2,1,21,3”,数组f的初值均为False,执行该程序段,f数组中元素值为True的个数有()A.1个B.2个C.3个D.4个30典型例题f(i)=TrueEnd IfNext i当数组元素a(1)到a(5)的值依次为“8,2,1,21,3”,数组f的初值均为False,执行该程序段,f数组中元素值为True的个数有(C)A.1个B.2个C.3个D.4个31典型例题解析逻辑类型数组 f(i)用于标记第 i 趟排序时,数组 a 中的元素是否有过交换。程序实现升序排序,其中 f(1)、

15、f(3)、f(4)的值为 true。所以答案选 C。3233易混易淆易混易淆冒泡排序与选择排序34 冒泡排序选择排序思想方法一边比较,一边交换先选出最大值或最小值,再交换核心代码For i=1 To n-1For j=n To i+1 Step-1If a(j)a(j-1)Thentemp=a(j-1)a(j-1)=a(j)a(j)=tempEnd IfNext j Next iFor i=1 To n-1k=iFor j=i+1 To n If a(j)a(k)Then k=jNext jIf ki Then temp=a(i)a(i)=a(k)a(k)=tempEnd IfNext i易混

16、易淆35 冒泡排序选择排序相同点n个数都需要n-1遍排序,其中变量i控制排序的遍数比较的次数一样多,都是(n-1)+(n-2)+3+2+1次最好的情况下,交换的次数一样,都是0次不同点边比较边交换,最坏的情况下交换的次数是(n-1)+(n-2)+3+2+1次先选择再交换,最坏的情况下交换的次数是n-1次如何区分因为是边比边交换,因此交换的三句代码是在内层循环里的。因为是先选出最大值或最小值,再交换,因此交换的三句代码是在内层循环的后面。典型例题例5数组a共由6个元素构成:49、45、61、46、58、57,经过如下程序处理后,m和n的值分别为()m=0:n=0For i=1 To 5k=iFo

17、r j=i+1 To 6If a(j)a(k)Then k=jm=m+136典型例题Next jIf k i Then t=a(i):a(i)=a(k):a(k)=t:n=n+1Next iA.15,4B.15,5C.30,4D.30,537典型例题Next jIf k i Then t=a(i):a(i)=a(k):a(k)=t:n=n+1Next iA.15,4B.15,5C.30,4D.30,5解析本题考查选择排序。通过阅读程序可知该程序是实现数组的递增排序,m存放总的比较次数,n存放数据交换次数。38典型例题例6阅读如下程序段:Dim flag(4)As BooleanDim i As

18、 Integer,j As IntegerFor i=1 To 4flag(i)=FalseNext ii=1Do While i=4 And flag(i)=False39典型例题For j=5 To i+1 Step-1If a(j)a(j-1)Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag(i)=TrueEnd IfNext ji=i+1Loop40典型例题数组a中元素依次为“5,4,3,2,1”,该程序执行后,数组flag中值为True的元素个数是()A.0B.2C.4D.1041典型例题数组a中元素依次为“5,4,3,2,1”,该程序执行后,数组flag中值为

19、True的元素个数是(C)A.0B.2C.4D.1042典型例题解析本题考查排序的应用。程序中的flag(i)是一个逻辑变量,如果第i遍有数据交换,则flag(i)=True。分析代码可知该程序采用了冒泡排序,升序。排序过程如表所示:因此4次冒泡排序都有数据交换。如果是选择排序,则只有第1遍和第2遍有数据交换。43 遍数(i)5,4,3,2,11 1,5,4,3,2 2 1,2,5,4,3 3 1,2,3,5,4 4 1,2,3,4,544真题在线真题在线1.(2018浙江4月学考+选考,16,3分)有一组正整数,要求供对其中的素数进行升序排序。排序后素数在前,非素数在后。排序示例如下。45排

20、序前 86 71 5 41 81 79 37 89排序后 5 37 41 71 79 89 86 81真题在线实现上述功能的VB程序如下,但加框处代码有错,请改正。Const n=8Dim a(1 To n)As IntegerPrivate Sub Command1_Click()Dim i As Integer,j As Integer,k As Integer,t As IntegerDim flag As Boolean读取一组正整数,存储在数组a 中,代码略46真题在线For i=1 To n-1k=1(1)If IsPrime(a(k)Then flag=True Else fla

21、g=FalseFor j=i+1 To nIf IsPrime(a(j)ThenIf a(j)a(k)Then(2)47真题在线k=jflag=TrueEnd IfEnd IfNext jIf k i Thent=a(k):a(k)=a(i):a(i)=tEnd If48真题在线If Not flag Then Exit For Exit For表示退出循环Next i依次输出排序后的数据。代码略End SubFunction IsPrime(m As Integer)As Boolean本函数判断m 是不是素数:是素数返回值为True,不是素数返回值为False代码略End Function

22、49真题在线答案(1)k=i(2)a(j)a(k)or flag=false50真题在线解析本题是选择排序的基础上加一个素数判断。程序的基本框架是选择排序,因此(1)处改为k=i。(2)最后结果是从小到大排,因此(2)处填a(j)a(k)貌似没错,但是要考虑到只排素数,素数放前面,非素数放后面,因此如果a(j)是素数,而a(k)是非素数,则一定要交换,将a(j)换到前面。第二种情况是,a(j)和a(k)都是素数,且a(j)a(k),此时也要交换。IsPrime函数是判断某个数是不是素数,如果是则返回值为true,否则为false。flag变量标记a(k)是不是素数,flag=true表示a(k)是素数,flag=false表示a(k)是非素数。51课堂总结教材研读重难突破一排序算法的基本思想二排序算法的程序实现突破 选择排序的变形