数据结构_选择排序_C.ppt

《数据结构_选择排序_C.ppt》由会员分享，可在线阅读，更多相关《数据结构_选择排序_C.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1010章章 内部排序内部排序10.1 10.1 排序的基本概念排序的基本概念10.2 10.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序10.7 10.7 各种内部排序方法的比较各种内部排序方法的比较10.4 10.4 选择选择排序排序基本思想：基本思想：第第i i趟在趟在n-i+1(i=1,2,n-i+1(i=1,2,n-1),n-1)个记录中选取个记录中选取关键字最小的记录作为有序序列中的第关键字最小的记录作为有序序列中的第i i个记录。个记录。1.1.简单选择排序

2、简单选择排序2.2.树形选择排序树形选择排序3.3.堆排序堆排序1 1）简单选择排序的基本思想）简单选择排序的基本思想 通过通过 n-in-i 次关键字间的比较，从无序序列次关键字间的比较，从无序序列 i.ni.n 的的 n-i+1 n-i+1 记录中选出关键字最小的记录加记录中选出关键字最小的记录加入有序序列（即作为有序序列中的第入有序序列（即作为有序序列中的第i i个记录）。个记录）。1.1.简单选择排序简单选择排序首先从首先从1-n1-n个元素中选个元素中选出关键字出关键字最小最小的记录交换的记录交换到到第一个第一个位置上。然后再位置上。然后再从第从第2 2 个到第个到第n n个元素中个

3、元素中选出次小的记录交换到选出次小的记录交换到第第二个二个位置上，依次类推。位置上，依次类推。初态初态8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 kijijik1 3 9 8 6 互换互换ij1 3 9 8 6 ij1 3 9 8 6 ij第第一一趟趟第第二二趟趟1 3 9 8 6 ij第第三三趟趟示例：示例：ijkkjk2 2）简单选择排序算法描述）简单选择排序算法描述void void SelectSortSelectSort(Elem R,(Elem R,intint n)n)/对记录序列对记录序列R1.nR1.n作简单选择排序作简单选择排序 for(

4、i=1;in;+i)for(i=1;iB，B-C=A-C例例锦标赛锦标赛在在8 8个运动员中决出前个运动员中决出前3 3名至多需要名至多需要1111场比赛场比赛CHACHALIU*CHACHAZHAODIAOWANGWANGXUEDIAOYANGDIAO亚军亚军例例锦标赛锦标赛在在8 8个运动员中决出前个运动员中决出前3 3名至多需要名至多需要1111场比赛场比赛DIAOLIULIU*ZHAO*DIAOWANGWANGXUEDIAOYANGDIAO季军季军2.2.树型选择排序树型选择排序1 1）基本思想）基本思想 又称锦标赛排序，又称锦标赛排序，其过程：其过程：首先对首先对n n个记录的关键字

5、两两比较，然后在个记录的关键字两两比较，然后在 n/2n/2 个个较小者之间再进行两两比较，如此重复，直至选出最小关较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。键字的记录为止。此对应的过程可以用一棵有此对应的过程可以用一棵有n n个叶子结点的个叶子结点的完全二叉完全二叉树树表示。表示。ABCDEFGHACEGAEAABCDEFACEGAEA493865977613274938651327381313例例 从从4949，3838，6565，9797，7676，1313，2727，4949 8 8个关键字中选出最小关键字的过程。个关键字中选出最小关键字的过程。输出输出1313

6、4938659776274938657627382727例例 从从4949，3838，6565，9797，7676，1313，2727，508508个关键字中选出最小关键字的过程个关键字中选出最小关键字的过程输出输出1313，272749386597764938657649384938例例 从从4949，3838，6565，9797，7676，1313，2727，508508个关键字中选出最小关键字的过程个关键字中选出最小关键字的过程输出输出1313，2727，3838除了最小关键字之外，每次选择比较的次数为：除了最小关键字之外，每次选择比较的次数为：完全二叉树的深度完全二叉树的深度 -1-1

7、 次次2 2）树型选择排序算法分析）树型选择排序算法分析 含含n n个叶子结点的完全二叉树的深度为个叶子结点的完全二叉树的深度为 2 2n n +1+1，因此在树型选择排序中，除了最小关键字之外，每选择，因此在树型选择排序中，除了最小关键字之外，每选择一个次小关键字仅需进行一个次小关键字仅需进行 2 2n n 次比较，因此，其时次比较，因此，其时间复杂度为间复杂度为 O(nO(n2 2n)n)。由于此种排序方法需要的存储空间较多和最大值多余由于此种排序方法需要的存储空间较多和最大值多余的比较多等缺点，的比较多等缺点，堆排序堆排序应运而生。应运而生。3.3.堆排序堆排序1 1）堆的定义堆的定义

8、n n个元素的个元素的序列序列kk1 1,k,k2 2,k,k3 3 ,k kn n 当且仅当满足关系：当且仅当满足关系：k ki i k k2i2i ，k ki i k k2i+12i+1 或或 k ki i k k2i 2i ，k ki i k k2i+12i+1 （i=1i=1，2 2，3 3，n/2n/2 ）则称之为则称之为堆堆。小根堆小根堆大根堆大根堆例如例如：判定序列判定序列9 96 6，8383，2727，3838，1111，0909、1212，3636，2424，8585，4747，3030，5353，9191是否是否堆堆969683832727383809091111将排序码

9、按顺序组成一棵完全二叉树，则易判别。小根堆：小根堆：二叉树的所有根结点值小于或等于左右孩子的值；二叉树的所有根结点值小于或等于左右孩子的值；大根堆：大根堆：二叉树的所有根结点值大于或等于左右孩子的值；二叉树的所有根结点值大于或等于左右孩子的值；121236362424858530304747535391912 2）堆排序的基本思想堆排序的基本思想 将堆中第一个结点（二叉树根结点）和最后一个结将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（点的数据进行交换（k k1 1与与k kn n），再将），再将k k1 1k kn-1n-1重新建堆重新建堆，然后然后k k1 1和和k kn-

10、1n-1交换，再将交换，再将 k k1 1k kn-2n-2重新重新建堆建堆，然后，然后k k1 1和和k kn-2n-2交换，如此重复下去，每次重新交换，如此重复下去，每次重新建堆建堆的元素个数不断减的元素个数不断减1 1，直到重新，直到重新建堆建堆的元素个数仅剩一个为止。这时堆排序的元素个数仅剩一个为止。这时堆排序已经完成，则排序码已经完成，则排序码k k1 1，k k2 2，k k3 3，k kn n已排成一个有序已排成一个有序序列。序列。实现堆排序需要解决两个问题：实现堆排序需要解决两个问题：(1)(1)如何由一个无序序列建成一个堆如何由一个无序序列建成一个堆?(2)(2)如何在输出堆

11、顶元素之后，调整剩余元素成如何在输出堆顶元素之后，调整剩余元素成为一个新的堆为一个新的堆?例：图例：图(a)是个堆，假设输出堆顶元素之后，以堆中最后是个堆，假设输出堆顶元素之后，以堆中最后一个元素替代之，如图一个元素替代之，如图(b)所示。此时根结点的左、右子所示。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。树均为堆，则仅需自上至下进行调整即可。这个自堆顶至叶子的调整过程称为这个自堆顶至叶子的调整过程称为“筛选筛选”。概念：概念：“筛选筛选”假若完全二叉树的某一个结点假若完全二叉树的某一个结点 i i，它的左、，它的左、右子树已是堆。需要将右子树已是堆。需要将R2i.keyR2i

12、.key与与R2i+1.keyR2i+1.key之中的最小者与之中的最小者与Ri.keyRi.key比较，若比较，若Ri.keyRi.key较大较大则交换，这有可能破坏下一级堆。于是继续采用则交换，这有可能破坏下一级堆。于是继续采用上述方法构造下一级堆，直到完全二叉树中结点上述方法构造下一级堆，直到完全二叉树中结点i i构成堆为止。这个自堆顶到叶子的调整过程为构成堆为止。这个自堆顶到叶子的调整过程为“筛选筛选”。void void HeapAdjust(SqListHeapAdjust(SqList H H，intint s s，intint m)m)/已知已知H.rs.mH.rs.m 中记录

13、的关键字除中记录的关键字除H.rs.keyH.rs.key之外均满足堆的定义，之外均满足堆的定义，/本函数调整本函数调整H.rsH.rs 的关键字，使的关键字，使H.rs.mH.rs.m 成为一个大顶堆成为一个大顶堆rcrc=H.rsH.rs;for(j=2*s;j=m;j*=2)for(j=2*s;j=m;j*=2)/沿沿keykey较大的孩子结点向下筛选较大的孩子结点向下筛选,j,j为为keykey较大的记录的下标较大的记录的下标 if(jif(jm&0;-i)=H.length/2;i0;-i)/把把H.r1.H.r1.lengthlength 建成大顶堆建成大顶堆HeapAdjust(

14、H,i,H.lengthHeapAdjust(H,i,H.length););for(ifor(i=H.lengthH.length;i1;-i);i1;-i)/将堆顶记录和当前未经排将堆顶记录和当前未经排 /序子序列序子序列H.r.1.iH.r.1.i中最后一个记录相互交换中最后一个记录相互交换H.r1 H.r1 H.riH.ri；HeapAdjust(H,1,i-1);HeapAdjust(H,1,i-1);/将将H.R1.i-1H.R1.i-1重新调整为大顶堆重新调整为大顶堆 /HeapSortHeapSort 4 4）堆排序的效率分析堆排序的效率分析 在整个堆排序中，共需要进行在整个堆

15、排序中，共需要进行 n+n+n/2n/2 -1 -1 次筛选次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度。故每次的比较和移动次数都不会超过完全二叉树的深度。故每次筛选运算的时间复杂度为筛选运算的时间复杂度为O(logO(log2 2n)n)，则整个堆排序过程的，则整个堆排序过程的时间复杂度为时间复杂度为O(nlogO(nlog2 2n)n)。堆排序在最坏情况下，时间复杂度也为堆排序在最坏情况下，时间复杂度也为O(nlogO(nlog2 2n)n)。相对于快速排序，这是堆排序的最大优点。此外，堆排序相对于快速排序，这是堆排序的最大优点。此外，堆排序仅需一个记录大小辅助存储空间供交换使用。仅需一个记录大小辅助存储空间供交换使用。由于存在着不相邻元素之间的互换，因此，堆排序是由于存在着不相邻元素之间的互换，因此，堆排序是一种一种不稳定不稳定的排序方法。的排序方法。