数据结构与算法--第23讲选择排序.ppt

《数据结构与算法--第23讲选择排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第23讲选择排序本讲知识点：(1)了解选择排序的思想(2)掌握选择排序、堆排序的算法(3)掌握选择排序的应用难点：堆排序2排序的基本概念各种排序方法各种排序方法的比较排序知识体系结构排序插入排序选择排序交换排序归并排序基数排序直接插入排序折半插入排序链表插入排序希尔排序直接选择排序堆排序冒泡排序快速排序3选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。有序序列r0r1ri-1rirn-1rk…………无序序列rn-1ri+1r0r1ri-1……riri……交换最

2、小记录一、简单选择排序SimpleSelectionSort4基本思想：首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束需解决的关键问题?⑴如何在待排序序列中选出关键码最小的记录？⑵如何确定待排序序列中关键码最小的记录在有序序列中的位置？一、简单选择排序SimpleSelectionSort5简单选择排序示例0821i=1最小者08交换21,08最小者16交

3、换25,16最小者21交换49,212128i=02516490808i=2210828492128491625161625一、简单选择排序SimpleSelectionSort6i=3最小者25交换25,28i=4最小者28不交换492108281625254921081628252849210816282528无序区只有一个记录简单选择排序示例一、简单选择排序SimpleSelectionSort7解决方法：设置一个整型变量lowIndex，用于记录在一趟比较的过程中关键码最小的记录位置。关键问题⑴：如何在无序区

4、中选出关键码最小的记录？212825164908lowIndexlowIndexlowIndex08一、简单选择排序SimpleSelectionSort8算法描述：lowIndex=i;for(j=i+1;j

5、的待排序区间是elem[i]~elem[n-1]，则elem[i]是无序区第一个记录，所以，将lowIndex所记载的关键码最小的记录与elem[i]交换。关键问题⑵：如何确定最小记录的最终位置？算法描述：if(lowIndex!=i)elem[i]←→elme[lwoIndex];一、简单选择排序SimpleSelectionSort10voidSimpleSelectionSort(ElemTypeelem[],intn){for(inti=0;i

6、i;for(intj=i+1;j

7、Onninni=-=-å-=）（简单选择排序的时间复杂度为O(n2)。13改进的着眼点：如何减少关键码间的比较次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。减少关键码间的比较次数查找最小值的同时，找出较小值二、堆排序HeapSort14堆的定义堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。1820323645253

8、85040281.小根堆的根结点是所有结点的最小者。2.较小结点靠近根结点，但不绝对。15堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。503845402836322018281.大根堆的根结点是所有结点的最大者。2.较大结点靠近根结点，但不绝