《第13周内排序第4讲-选择排序.pdf》由会员分享，可在线阅读，更多相关《第13周内排序第4讲-选择排序.pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、常见的选择常见的选择排序方法排序方法： （1）简单选择排序简单选择排序（或称直接选择排序或称直接选择排序） （2）堆排序堆排序 基本思路基本思路 全局有序区全局有序区无序区无序区 选出最小记录选出最小记录Rk 10.4.1 简单选择排序简单选择排序 从从ai.n- -1中选出最小中选出最小元素元素： int Min(int a,int n,int i) int k=i, j;/k保存最小元素的下标保存最小元素的下标 for (j=i+1;jn;j+) if (ajak) k=j; return ak; 简单选择简单选择n个记录中找最小记录需要个记录中找最小记录需要n- -1次比较次比较 全局有
2、序区全局有序区 R0 Ri- -1 无序区无序区 RiRn- -1 全局有序全局有序区区 R0 Ri- -1 Ri 无序区无序区 Ri+1 Rn- -1 采用简单选择方法采用简单选择方法选出最小记录选出最小记录 初始初始时时，全局有序区为空全局有序区为空 i0 n- -2，共经过共经过n- -1趟排序趟排序 基本思路基本思路 void SelectSort(RecType R,int n) int i,j,k; RecType tmp; for (i=0;in-1;i+)/做第做第i趟排序趟排序 k=i; for (j=i+1;jn;j+) if (Rj.keyRk.key) k=j; if
3、(k!=i)/RiRk tmp=Ri; Ri=Rk; Rk=tmp; 简单选择排序算法简单选择排序算法 在Ri.n-1中采用 简单选择方法选 出最小的Rk 初始关键字初始关键字 21345 12345 i=0 12345 i=1 12345 i=2 12345 i=3 采用简单选择排序方法对采用简单选择排序方法对(2，1，3，4，5) 进行排序进行排序 任何情况下任何情况下：都有做都有做n- -1趟趟！ 没有记没有记 录移动录移动 移动移动记录的次数记录的次数，正序正序为最小值为最小值 0，反序反序为最大值为最大值3(n- -1) 。 对对 n 个记录进行简单选择排序，所需进行个记录进行简单选
4、择排序，所需进行的的关键字的关键字的比较次比较次 数数 总计为：总计为： 2 1 1 2 0 )n(n )in( n i 简单选择排序的最好简单选择排序的最好、最坏和平均时间复杂度为最坏和平均时间复杂度为O(n2)。 算法分析算法分析 从从i个记录中挑选最小记录需要比较个记录中挑选最小记录需要比较i- -1次次。 第第i（i=0n- -2）趟从趟从n- -i记录中挑选最小记录需要比较记录中挑选最小记录需要比较n- -i- -1。 10.4.2 堆排序堆排序 全局有序区全局有序区无序区无序区 选出最小记录选出最小记录Rk 采用堆方法采用堆方法选出最小记录：选出最小记录：堆排序算法堆排序算法 基本
5、思路基本思路 一个序列一个序列R1.n，关键字分别为，关键字分别为k1、k2、kn。 1、堆堆的定义的定义 该序列满足如下性质该序列满足如下性质（简称为堆性质简称为堆性质）：）： kik2i且且kik2i+1 或或 kik2i且且kik2i+1（1i n/2 ） 满足第满足第种情况的堆称为种情况的堆称为小根堆小根堆，满足第满足第种情况的堆称为大根堆种情况的堆称为大根堆。 下面讨论的堆是下面讨论的堆是大根堆大根堆。 a1 a2a3 an 完全二叉树完全二叉树 i 2i2i+1 左孩子左孩子右孩子右孩子 大大根堆：根堆：对应的完全二叉树中，任意一个节点的关键字都大于或对应的完全二叉树中，任意一个节
6、点的关键字都大于或 等于它的孩子节点的等于它的孩子节点的关键字。关键字。 最小关键字的记录一定是最小关键字的记录一定是某个叶子节点某个叶子节点！ 层序编号方式层序编号方式： a1a2 an 将序列将序列a1a2 an看成是一颗完全二叉树看成是一颗完全二叉树 12 95 413 n=6 如何如何判断判断一颗一颗完全二叉树是否为完全二叉树是否为大根堆大根堆 1 2 4 3 5 6 从编号为从编号为n/2=3的节点开始，的节点开始， 逐一判断所有分支节点逐一判断所有分支节点 所有分支节点满足定义所有分支节点满足定义 为为大根堆大根堆 堆排序的关键是构造堆堆排序的关键是构造堆，这里采用这里采用筛选算法
7、筛选算法建堆建堆。 所谓所谓“筛选筛选”指的是指的是，对一棵左对一棵左/右子树均为堆的完全二叉树右子树均为堆的完全二叉树， “调整调整”根节点使根节点使整个二叉树也成为一个堆整个二叉树也成为一个堆。 堆堆 堆堆 筛 选 筛 选 2、堆、堆排序算法设计排序算法设计 堆堆 筛选筛选 2 95 413 是 一 个 堆 是 一 个 堆 是 一 个 堆 是 一 个 堆 筛选筛选：不是不是堆堆 堆堆 从从根开始筛选根开始筛选 大根堆大根堆 仅仅处理从根节点仅仅处理从根节点某个叶子节点路径上的节点某个叶子节点路径上的节点 n个节点的个节点的完全二叉树高度为完全二叉树高度为 log2(n+1) 所有所有筛选的
8、时间复杂度为筛选的时间复杂度为O(log2n) tmp low 2*low2*low+1 high 筛选算法筛选算法 sift(RecType R, int low, int high)：Rlow . . high Rlow.high 根根 最后节点最后节点 void sift(RecType R,int low,int high) /调整堆的算法调整堆的算法 int i=low, j=2*i;/Rj是是Ri的左孩子的左孩子 RecType tmp=Ri; while (j=high) if (jhigh if (tmp.key=1;i-) /循环建立初始堆循环建立初始堆 sift(R,i,n
9、); 最大记录最大记录 筛选步骤筛选步骤： sift(R,3,6) sift(R,2,6) sift(R,1,6) 6 35 214 1 2 4 3 5 6 最大记录归位最大记录归位 4，3，5，2，1，6 最大记录最大记录6归位归位 R1 Ri 4 35 21 1 2 4 3 5 6 5 4 R1 Ri- -1 再对再对R1.i- -1的记录进行筛选的记录进行筛选 堆排序算法：堆排序算法： void HeapSort(RecType R,int n) int i; RecType tmp; for (i=n/2;i=1;i-)/循环建立初始堆循环建立初始堆 sift(R,i,n); for
10、(i=n; i=2; i-)/进行进行n-1次循环次循环,完成推排序完成推排序 tmp=R1;/R1 Ri R1=Ri; Ri=tmp; sift(R,1,i-1);/筛选筛选R1节点节点,得到得到i-1个节点的个节点的堆堆 【 例例 10- -5】 设 待 排 序 的 表 有设 待 排 序 的 表 有 10 个 记 录个 记 录 ， 其 关 键 字 分 别 为其 关 键 字 分 别 为 6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的过程说明采用堆排序方法进行排序的过程。 排序序列排序序列：6，8，7，9，0，1，3，2，4，5 8 9 524 013 7 6 看成是一棵
11、完全二叉树看成是一棵完全二叉树 调整成初始大调整成初始大根根堆堆： 8 9 524 013 7 6 调整完毕，成为一个大根堆调整完毕，成为一个大根堆 9 8 7 6 5 1 3 2 4 0 8 6 024 513 7 9 输出输出9（归位归位） 6 4 20 513 7 8 0 8 7 6 5 1 3 2 4 9 第第1趟排序趟排序 6 4 20 513 7 8 输出输出8（归位）（归位） 6 4 2 510 3 7 0 6 7 4 5 1 3 2 8 9 第第2趟排序趟排序 其他各趟排序依此进行其他各趟排序依此进行 0 1 2 3 4 5 6 7 8 9 最终结果：最终结果： 对高度对高度为
12、为 h 的的堆堆，一次一次“筛选筛选”所需进行的所需进行的关键字比较关键字比较的次数至多的次数至多 为为2(h- -1)。 调整“堆顶”调整“堆顶” n- -1 次，总共进行的次，总共进行的关键字比较关键字比较的次数的次数不不超过：超过： 2 ( log2(n- -1) + log2(n- -2) +log22) 2n( log2n ) 因此因此，堆排序的时间复杂度为堆排序的时间复杂度为O(nlogn)。 对对 n 个关键字个关键字，建成高度建成高度为为h（= log2n +1）的的堆堆，所所需进行的关键需进行的关键 字比较的次数不字比较的次数不超过超过4n。 3、堆堆排序算法分析排序算法分析
13、 空间复杂度为空间复杂度为O(1)，不稳定。，不稳定。 数据结构数据结构经典算法的启示经典算法的启示 简单选择排序算法简单选择排序算法 堆排序堆排序算法算法 利用了连续多次查找最大记录的特性利用了连续多次查找最大记录的特性 在操作系统中在操作系统中，将多个进程放在一个队列中将多个进程放在一个队列中，每个进程有一个优每个进程有一个优 先级先级，总是出队优先级最高的进程执行总是出队优先级最高的进程执行。 采用采用优先队列优先队列，用用堆堆来实现来实现！ 【例例10- -6】设有设有1000个无序的整数个无序的整数，希望用最快的速度挑选出希望用最快的速度挑选出 其中前其中前10个最大的元素个最大的元素，最好选用最好选用排序方法排序方法。 A.冒泡排序冒泡排序B.快速排序快速排序 C.堆排序堆排序D.直接插入排序直接插入排序 n=1000，k=10 冒泡排序的大致时间：冒泡排序的大致时间：kn 堆排序的大致时间：堆排序的大致时间：4n+klog2n。 本讲完本讲完