数据结构选择排序C.ppt

《数据结构选择排序C.ppt》由会员分享，可在线阅读，更多相关《数据结构选择排序C.ppt（32页珍藏版）》请在课桌文档上搜索。

1、第10章 内部排序10.1 排序的基本概念10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序10.7 各种内部排序方法的比较,10.4 选择排序,基本思想：第i趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。,1.简单选择排序2.树形选择排序3.堆排序,1）简单选择排序的基本思想 通过 n-i 次关键字间的比较，从无序序列i.n的 n-i+1 记录中选出关键字最小的记录加入有序序列（即作为有序序列中的第i个记录）。,1.简单选择排序,首先从1-n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到

2、第n个元素中选出次小的记录交换到第二个位置上，依次类推。,初态,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3 9 8 6,1 3 9 8 6,1 3 9 8 6,示例：,2）简单选择排序算法描述void SelectSort(Elem R,int n)/对记录序列R1.n作简单选择排序 for(i=1;in;+i)/选择第i小记录换到位置i k=SelectMinKey(R,i);if(i!=k)RiRk;/SelectSort,3）简单选择排序算法分析 由于存在着不相邻元素之间的互换，因此，简单选择排序是“不稳定的”。算法实现共需要进行 n-1 次选

3、择，每次选择需要进行n-i次比较（1in-1），而每次交换最多需3次移动，因此，总的比较次数 C=n(n-1)/2，总的移动次数 M=3(n-1)。故其时间复杂度为O(n2)。选择排序的主要操作是进行关键字间的比较，因此改进选择排序应从如何减少“比较”考虑。,显然，在n个关键字中选出最小值，至少进行n-1次比较，然而，继续在剩余的n-1个关键字中选择次小值，是否一定要进行n-2次比较呢？如果能利用前n-1次比较所得信息，就可减少以后各趟选择排序中所用的比较次数。实际上，体育比赛中的锦标赛便是一种选择排序,例 锦标赛在8个运动员中决出前3名至多需要11场比赛,前提：A-B，B-C=A-C,例 锦

4、标赛在8个运动员中决出前3名至多需要11场比赛,例 锦标赛在8个运动员中决出前3名至多需要11场比赛,2.树型选择排序1）基本思想 又称锦标赛排序，其过程：首先对n个记录的关键字两两比较，然后在 n/2 个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。此对应的过程可以用一棵有n个叶子结点的完全二叉树表示。,例 从49，38，65，97，76，13，27，498个关键字中选出最小关键字的过程。,输出13,例 从49，38，65，97，76，13，27，508个关键字中选出最小关键字的过程,输出13，27,例 从49，38，65，97，76，13，27，508个关键字中选出最小

5、关键字的过程,输出13，27，38,除了最小关键字之外，每次选择比较的次数为：完全二叉树的深度-1 次,2）树型选择排序算法分析 含n个叶子结点的完全二叉树的深度为 2n+1，因此在树型选择排序中，除了最小关键字之外，每选择一个次小关键字仅需进行 2n 次比较，因此，其时间复杂度为 O(n2n)。由于此种排序方法需要的存储空间较多和最大值多余的比较多等缺点，堆排序应运而生。,3.堆排序1）堆的定义 n个元素的序列k1,k2,k3,kn当且仅当满足关系：ki k2i，ki k2i+1 或 ki k2i，ki k2i+1（i=1，2，3，n/2）则称之为堆。,小根堆,大根堆,例如：判定序列96，8

6、3，27，38，11，09、12，36，24，85，47，30，53，91 是否堆,将排序码按顺序组成一棵完全二叉树，则易判别。,小根堆：二叉树的所有根结点值小于或等于左右孩子的值；大根堆：二叉树的所有根结点值大于或等于左右孩子的值；,2）堆排序的基本思想 将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1kn-1重新建堆，然后k1和kn-1交换，再将 k1kn-2重新建堆，然后k1和kn-2交换，如此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成，则排序码k1，k2，k3，kn已排成一个有序序列。,实现堆排序

7、需要解决两个问题：(1)如何由一个无序序列建成一个堆?(2)如何在输出堆顶元素之后，调整剩余元素成为一个新的堆?,例：图(a)是个堆，假设输出堆顶元素之后，以堆中最后一个元素替代之，如图(b)所示。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。,这个自堆顶至叶子的调整过程称为“筛选”。,概念：“筛选”假若完全二叉树的某一个结点 i，它的左、右子树已是堆。需要将R2i.key与R2i+1.key之中的最小者与Ri.key比较，若Ri.key较大则交换，这有可能破坏下一级堆。于是继续采用上述方法构造下一级堆，直到完全二叉树中结点i构成堆为止。这个自堆顶到叶子的调整过程为“筛选”。,vo

8、id HeapAdjust(SqList H，int s，int m)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，/本函数调整H.rs的关键字，使H.rs.m成为一个大顶堆rc=H.rs;for(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选,j为key较大的记录的下标 if(jm/插入/HeapAdjust,筛选的算法,3）建堆 将排序码 k1,k2,k3,kn 表示成一棵完全二叉树，然后从第 n/2 个排序码（即最右边的非终端结点）开始筛选，使由该结点作为根结点组成的子二叉树符合堆的定义，然后从第 n/2-1个排序码重复刚才操作，直到第一个排序码（

9、即根）止。这时候，该二叉树符合堆的定义，初始堆已经建立。,例：关键字序列T=(21，25，49，25，16，08），请建大根堆。,为便于理解，先将原始序列画成完全二叉树的形式。,21,i=3:,49,而且21还应当向下比较！,i=1:21小于25和49，要调整！,49大于08，不必调整；,i=2:25大于等于25和16，不必调整；,完全二叉树的最右一个非终端结点编号必为n/2！,例：对以上建好的大根堆进行排序：,交换 1号与 6 号记录 r0 rn,08 25 21 25 16 49,从 1 号到 5 号 重新调整为最大堆,08,25,25,08,从 1号到 4号 重新调整为最大堆,16,25

10、,从 1 号到 3号 重新调整为最大堆,从 1 号到 2 号 重新调整为最大堆,堆排序算法,void HeapSort(HeapType/将H.R1.i-1重新调整为大顶堆/HeapSort,4）堆排序的效率分析 在整个堆排序中，共需要进行 n+n/2-1 次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度。故每次筛选运算的时间复杂度为O(log2n)，则整个堆排序过程的时间复杂度为O(nlog2n)。堆排序在最坏情况下，时间复杂度也为O(nlog2n)。相对于快速排序，这是堆排序的最大优点。此外，堆排序仅需一个记录大小辅助存储空间供交换使用。由于存在着不相邻元素之间的互换，因此，堆排序是一种不稳定的排序方法。,