《排序算法及应用》PPT课件

《《排序算法及应用》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六讲　排序算法及应用排序算法的种类：1、选择排序2、冒泡排序3、插入排序4、快速排序5、堆排序1、选择排序算法基本思想：对待排序的序列进行n-1遍处理：第1遍处理是从a[1],a[2],……a[n]中选择最小的放在a[1]位置；第2遍处理是从a[2],a[3],……a[n]中选择最小的放在a[2]位置；……第I遍处理是将a[i],a[i+1],……a[n]中最小的数与a[i]交换位置，这样经过第i遍处理后，a[i]是所有的中的第i小。即前i个数就已经排好序了。N-1遍处理后，剩下的最后一个一定是最大的，不需要

2、再处理了。a:待排序的数组；//从小到大排序简单选择排序：fori:=1ton-1do{从第一个元素开始,进行n-1遍处理}forj:=i+1tondo{第i遍处理}Ifa[i]>a[j]then{交换a[i]和a[j]}begint:=a[i];a[i]:=a[j];a[j]:=t;end;算法的改进:减少交换次数fori:=1ton-1dobegink:=i;forj:=i+1tondoifa[j]ithenbegint:=a[k];a[k]:=a[i];a[i]

3、:=t;end;end;排序的关键字：20301015161382、冒泡排序算法：基本思想：（从小到大排序）将待排序的数据看作竖派排的一列”气泡“，小的数据比较轻，从而要上浮。共进行n-1遍处理，每一遍处理，就是从底向上检查序列，如果相邻的两个数据顺序不对，即轻（小）的在下面，就交换他们的位置。第一遍处理完后，“最轻”的就浮到上面。第二遍处理完后，“次轻”的就浮到上面。共需要n-1遍处理即完成排序。//简单的冒泡排序fori:=1ton-1doforj:=ndowntoi+1doifa[j]

4、nbegint:=a[j];a[j]:=a[j-1];a[j-1]:=t;end;//判断标志：flag=true已有序//改进后的冒泡排序fori:=1ton-1dobeginflag:=true;forj:=ndowntoi+1doifa[j]

5、通过访问MemL[Seg0040:$006C]来获取当前时间，它返回的是当日零时到现在所经过的时间，单位约为55毫秒（约1/18.2秒）。测定<语句组2>执行的时间Starttime,endtime:longint;Starttime:=MemL[Seg0040:$006C];<语句组2>endtime:=MemL[Seg0040:$006C];Writeln((endtime-starttime)/18.2:0:2);语句组2运行的时间或：Writeln((MemL[Seg0040:$006C]-startt

6、ime)/18.2:0:2);StartTime:=MemL[Seg0040:$006C];fori:=1ton-1doforj:=ndowntoi+1doifa[j]

7、,……,a[i-1]的适当的位置，从而使得a[1],a[2],……,a[i-1],a[i]又是排好的序列。a:array[0..n]ofinteger;{a[0]记录当前待插元a[i]}fori:=2tondobegina[0]:=a[i];{取第i个元素作为待插入元素}j:=i-1;{从已排好的最后一个a[i-1]开始比较}whilea[0]=a[j]时循环结束}a[j

8、+1]:=a[0];{在第j+1个位置插入a[i]元素}end;4、快速排序算法：基本思想：把待排序的n个元素放到一个中的任一个元素数组中，先取数组中的某一个元素作为一个基准元素，把这个元素放到数组中合适的位置，同时对其他元素进行调整，使得在这个基准元素的右边的所有元素都比这个基准元素大，而基准元素左边的元素都比它小。也就是说，这个基准元素当前所在的位置就是排序后的最终位置。然后再对基