资源描述：
《数据结构第10章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十章内部排序概述内部排序：待排序记录存放在计算机内存中进行的排序过程。外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。稳定的排序方法：假设Ki=Kj，且在排序前Ri领先于Rj。若排序后Ri仍领先于Rj，称为稳定的排序方法；反之，为不稳定的排序方法。分类：按排序过程分：插入排序，交换排序，选择排序，归并排序，基数排序。按所需工作量分：简单的排序方法O(n2)先进的排序方法O(nlog(n))基数排序O(d*n)内部排序插入排序交换排序选择排序归并排序基数排序有序表中插入元素，并保持其有序将表中关键字比较，位置不对交换先查找关键字，
2、再交换。将两个有序的关键字序列进行归并不比较，按多关键字排序方法直接折半2-路表希尔冒泡快速简单树型堆直接插入排序例：给定以下关键字：初始状态(49)38659776132749‘i=2(38)(3849)659776132749‘i=3(65)(384965)9776132749‘i=4(97)(38496597)76132749‘i=5(76)(3849657697)132749‘i=6(13)(133849657697)2749‘i=7(27)(13273849657697)49‘i=8(49’)(1327384949’657697)监视哨L.r[0]表插入排序012345678
3、max4938659776132749‘10key域next域120304452627382-路插入排序例：给定以下关键字：初始状态4938659776132749‘i=1(49)i=2(49)(38)i=3(4965)(38)i=4(496597)(38)i=5(49657697)(38)i=6(49657697)(1338)i=7(49657697)(132738)i=8(4949’657697132738)finalfirst希尔排序例：给定以下关键字：初始状态4938659776132749‘5504491338276549‘97557604一趟排序结果：132749’5504
4、49386597761355387627046549‘4997二趟排序结果：130449382749‘55659776三趟排序结果：041327384949‘55657697快速排序例：给定以下关键字：初始状态4938659776132749‘进行一次交换后2738659776134949‘进行二次交换后2738499776136549‘进行三次交换后2738139776496549‘进行四次交换后2738134976976549‘第一趟结果{273813}49{76976549‘}第二趟结果{13}27{38}{49‘65}76{97}第三趟结果49‘{65}结果{132738494
5、9‘657697}ijiiiiiijjjjjjj冒泡排序例：给定以下关键字：49383838381313384949491327276565651327383897761327494976132749‘49‘132749‘652749‘7649‘97初始一趟二趟三趟四趟五趟六趟状态例：给定以下关键字：初始状态4938659776132749‘第一趟1338659776492749‘第二趟1327659776493849‘第三趟1327389776496549‘第四趟1327384976976549‘最后1327384949657697简单选择排序树型选择排序例：给定以下关键字：4938
6、659776132749‘38651327381313说明：13为最小关键字，将其与第一个关键字交换。然后，将13用∞替代继续上述比较，找到余下的最小至27树型选择排序例：给定以下关键字：4938659776∞2749‘38657627382727优点：减少比较次数，缺点：辅助空间用得太多，与∞比较没有必要。堆排序堆定义堆排序建立堆定义：n个元素的序列{k1,k2,…,k3}当且仅当满足下列关系时，称为堆：ki≤k2i或ki≥k2iki≤k2i+1ki≥k2i+1（i=1,2,…,[n/2])将此序列对应的一维数组完全二叉数9683270911381236245330478591{96
7、,83,27,38,11,09}{12,36,24,85,47,30,53,91}堆排序13382749657649’97筛选97382749657649’131234567813382749‘7665499797139727972749974997972797273897973849’979749‘38653865654949654949’6597764949‘657697建立堆4938652713769749’筛选1234567849386
