数据结构第10章 内部排序讲解.ppt

利用堆的特性进行的排序方法即为“堆排序” 其排序过程如下：　假设待排关键字序列为： { 34, 39, 20, 65, 47, 12, 98, 73, 81, 56 } 　1）先将它调整为大顶堆：{ 98, 81, 34, 73, 56, 12, 20, 39, 65, 47 } 　2）互换“堆顶”和待排序列中 的最后的关键字： { 47, 81, 34, 73, 56, 12, 20, 39, 65, 98 } 3）在待排序列中舍去最大关键字，将其余部 分重新调整为堆 { 81, 73, 34, 65, 56, 12, 20, 39, 47 } 98 4）重复2）和3）直至待排序列中只剩一个关键字为止。 　可见，堆排序的两个关键问题是： 1） 如何将一个无序序列调整为堆？2）如何在互换堆顶之后重新调整为堆？ 先讨论第二个问题:只要 “从上到下” 进行 “筛选” 可将该序列重新调整为大顶堆。如动画flash10-4-2 如何建堆？ 建堆的过程是一个从下到上调整堆的过程。 例如动画 flash10-4-4所示对无序序列进行建堆的过程。 教材p282 算法10.10 调整堆的过程 教材p282 算法10.11 堆排序过程 堆排序的时间复杂度分析 1）对深度为k的堆，筛选所进行的关键字比较的次数至多为2(k-1)。 2）对n个关键字建成深度为h的堆，所需进行的关键字比较的次数至多为4(n)。 3）调整堆顶n-1次，总共进行的关键字比较次数不超过 堆排序的时间复杂度为O(nlogn) * * 10.1 排序的定义和方法 什么是“排序”？ 简单说，排序是将无序的记录序列调整为有序记录序列的一种操作。 例如，将下列记录序列　　{ 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 }  调整为序列　　{ 14, 23, 36, 49, 52, 58, 61, 75, 80, 97 } 第十章 内部排序 一般情况下，对排序的定义为： 　　假设含有n个记录的序列为： { r1,r2,…,rn} (10-1) 它们的关键字相应为 {k1, k2,…,kn} 对式（10-1）的记录序列进行排序就是要确定序号1,2,…,n的一种排列 P1,P2,…,Pn 使其相应的关键字满足如下的非递减（或非递增）的关系： (10-2) 　　　 ?????????????????????? 就是使式(10-1)的记录序列重新排列成一个按关键字有序的序列 { rp1,rp2,…,rpn } (10-3) 当待排序记录中的关键字 ?(i=1,2,…,n)都不相同时，则任何一个记录的无序序列经排序后得到的结果是唯一； 若待排序的序列中存在两个或两个以上关键字相等的记录，则排序所得到的结果不唯一。 假设ki=kj (1≤i≤n,1≤j≤n,i≠j)， 且在排序前的序列中，ri 领先于 rj(即ij)。 若在排序后的序列中 ri 仍领先于 rj， 则称所用的排序方法是稳定的； 反之，若可能使排序后的序列中 rj领先于 ri?， 则称所用的排序方法是不稳定的 根据涉及的存储器不同，将排序方法分为两大类： 1）内部排序：在排序进行的过程中不使用计算机外部 存储器的排序过程。 2）外部排序：在排序进行的过程中需要对外存进行访 问的排序过程。 内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程 无序序列 有序序列 无序序列 有序序列 一趟排序 逐步扩大记录的有序序列长度排序的方法大致有一下几类 ： 插入类、交换类、选择类、归并类、其他类 将无序子序列中的一个或几个记录插入到有序序列中从而增加记录的有序子序列的长度 通过交换无序序列中的记录，