chapter9 内部排序.ppt

数 据 结 构 9.4 选择类排序 第 9 章 内部排序 从记录的无序子序列中“选择”关键字最小或 最大的记录，并将它加入到有序子序列中， 以此方法增加记录的有序子序列的长度。 ①简单选择排序 ③堆排序 ②树型选择排序 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ①简单选择排序 98 35 14 55 77 35 62 48 i 第 1 趟 k j j k j j j k j j 14 48 2 i k j 35 62 3 35 62 4 48 77 5 55 6 62 77 7 77 8 98 void SelectSort(RecordType r[ ],int n) { n=length; for(i=1;i=n-1;i++) { k=i; for(j=i+1;j=n; ++j) if(r[j].keyr[k].key) k=j; if(k!=i) { x=r[i];r[i]=r[k];r[k]=x;} } } 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ①简单选择排序 时间性能分析 对 n 个记录进行简单选择排序，所需进 行的关键字间的比较次数 总计为： 移动记录的次数，最小值为 0, 最大值为3(n-1) 。 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ②树型选择排序 是一种按锦标赛的思想进行排序的方法。 49 38 27 65 97 76 49 13 38 65 13 27 38 13 13 ∞ 76 13 27 27 27 ∞ 49 49 38 38 ∞ 49 49 49 49 ∞ ∞ 65 49 49 ∞ ∞ 76 65 65 ∞ 97 97 76 76 ∞ ∞ ∞ 97 97 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 对树型排序的进一步改进。 堆是满足下列性质的数列{r1, r2, …，rn}： 或 堆的定义: {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 例如: 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 (小顶堆) (大顶堆) ? í ì ￡ ￡ + 1 2 2 i i i i r r r r ? í ì 3 3 + 1 2 2 i i i i r r r r ri r2i r2i+1 若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。 例如: 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 12 36 27 65 40 34 98 81 73 55 49 14 14 是小顶堆 不 堆排序即是利用堆的特性对记录序列进行排序。 例如： 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 交换 98 和 12 重新调整为大顶堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 经过筛选 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 1、如何由一个无序序列“建初堆”？ 堆排序的两个问题: 2、输出堆顶后，如何“筛选”？ 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 所谓“筛选”指的是，对一棵左/右子树均为堆的完全 二叉树，“调整”根结点使整个二叉树也成为一个堆。 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 48 98 35 77 55 14 35 62 48 98 77 62 48 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 例如： { 48, 62, 35, 77, 55, 14, 35, 98} 48 62 35 77 55 14 35 98 显然不是一个堆 调整 如何建初堆？ * 数 据 结 构 9.1 排序的基本概念 9.2 插入类排序 9.4 选择类排序 第 9 章 内部排序 9.3 交换类排序 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的总和比较 数 据 结 构 9.1排序的基本概念 第 9 章 内部排序 排序是计算机内经常进行的一种操作，其目的是将