数据结构课件-排序.ppt

《数据结构课件-排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、假定一个线性表（38，52，25，74，68，16，30，54，90，72),画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度；并画出删除结点74后的二叉树。1题：表长为12的哈希表中已填有关键字17，60，29的记录，H(key)=key%11,现有第4个记录，其关键字为38，按线性探测再散列和二次探测再散列的方法处理冲突，并将38填入表中。601729012345678910112题：关键字（19,14,23,1,18,20,84),表长为8的哈希表中，H(key)=key%7,设每个记录的查找概率相等，构造哈希表，按线性探测再散列和二

2、次探测再散列的方法处理冲突。012345673第10章内部排序10.1概述10.2插入排序10.3快速排序10.4选择（交换）排序10.5归并排序4排序——是将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。排序的基本操作：比较关键字的大小将记录从一个位置移动到另一个位置5稳定排序方法——假设Ki=Kj(1<=i,j<=n,i<>j),且在排序前的序列中Ri领先于Rj，若在排序后的序列中Ri仍领先Rj，则称所用的排序方法是稳定的。不稳定排序方法——假设Ki=Kj(1<=i,j<=n,i<>j),且在排序前的序列中Ri领先于Rj，若在排序后的序列中

3、Rj领先Ri，则称所用的排序方法是不稳定的。6待排序记录存放在计算机随机存储器中进行的排序过程；内部排序——待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程；外部排序——710.2插入排序插入排序直接插入排序2-路插入排序折半插入排序希尔排序10.2.1直接插入排序基本操作：直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。8例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27)，对其进行排序，写出每一趟结果。9直接插入排序的过程:

4、[初始关键字]r[1]r[2]r[3]r[4]r[5]r[6]r[7](49)386597761327第一趟插入(3849)6597761327第二趟插入(384965)97761327第三趟插入(38496597)761327第四趟插入(3849657697)1327第五趟插入(133849657697)27第六趟插入(13273849657697)38659776132710题：用直接插入法对{45，76，34，85，11，69，48}进行排序，写出每一趟的结果。11折半插入排序在折半插入排序过程中，目的是查询插入点结束查找过程条件都是high

5、插入位置为low所示的地方(133849657697)27lowhighmid122-路插入排序在折半插入排序基础上改进，减少排序过程中移动的次数设两个指针first和final，分别指示排序中得到的最小和最大的记录13d[1]d[2]d[3]d[4]d[5]d[6]d[7]d[8][初始关键字]4938659776132749`i=1:49first↑↑finali=2:4938first↑↑finali=3:493865↑finalfirst↑i=4:49386597↑finalfirst↑i=5:4938657697↑finalfirst↑i=6:4

6、93865769713↑finalfirst↑i=7:49386576971327↑finalfirst↑i=8:4949`657697132738↑final↑first14希尔排序(缩小增量）基本思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)分别按增量为3、2、1进行希尔排序15[初始关键字]r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]49386

7、59776132749`第一趟排序后:(d1=3)2738134949`659776第二趟排序后:(d2=2)132749`97第三趟排序后:(d3=1)1327384949`6576973849657616希尔排序：关键字较小的记录不是一步步的移动，而是跳跃式的往前移动从而在进行最后一趟增量为1的插入排序时，序列已基本有序，做少量的比较和移动即可使增量序列中的值没有除1之外的公因子，并且最后一趟增量值必须为1。17题：用希尔排序法对{45，76，34，85，11，69，48}进行排序，增量的取值分别为3，2，1写出每一趟的结果。1810.3快速（交换）排

8、序起泡（冒泡）排序的基本思想:首先将第一个记录的关键字和第二个记录