考研数据结构chpt10.pptVIP

第十章 内部排序 10.4 选择排序 ⒊ 调整方法 ⑴ 将堆顶元素和堆的最后一个元素位置交换； ⑵ 然后以当前堆顶元素和其左、右子树的根结点进行比较(此时，左、右子树均为堆)，并与值较小的结点进行交换； ⑶ 重复⑵，继续调整被交换过的子树，直到叶结点或没进行交换为止。 称这个调整过程为筛选。 * * 基本概念 插入排序 快速排序 选择排序 归并排序 基数排序 10.1 基本概念 设含有n个记录的文件{R1,R2,...,Rn}，其相应的关键字为{K1,K2,...,Kn}，将记录按关键字值非递减(或非递增)顺序排列的过程，称为排序。 对所有的Ki=Kj (i≠j),若排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称该排序方法是稳定的，反之，称为不稳定 的。 稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置（即领先关系）是否变化。 10.1 基本概念 内部排序：待排序文件的全部记录存放在内存进行的排序，称为内部排序。 外部排序：排序过程中需要进行内外存数据交换的排序，称为外部排序。 10.1 基本概念 内排序分类 按排序过程依据的原则分为：插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分：简单排序 O(n2) 先进排序 O(nlogn) 基数排序 O(d．n) 10.2 插入排序 一. 直接插入排序 (最简单的排序方法） ⒈ 基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置(有序子文件记录数增1) 例如：已有待排序文件为：38，65，49，76，97 首先将文件的第一个记录，视为有序文件，然后从第二个记录开始，直到最后一个记录，依次将他们插入到有序文件的合适位置。 10.2 插入排序 ⒉ 直接插入排序算法 PROC strainsort(VAR r:filetype)； FOR i:=2 TO n DO [ r[0]:=r[i]; j:=i-1; {r[1]～r[i-1]为有序子文件} WHILE r[0].key＜r[j].key DO [ r[j+1]:=r[j]; j:=j-1 ]; {确定插入位置并移动} r[j+1]:=r[0] ] ENDP; {strainsort} 10.2 插入排序 ⒊ 算法分析 ⑴ 空间上，只需i，j两个整型变量和一个记录的辅助空间r[0], r[0]作为“监视哨”，控制待插入元素相对于有序子文件为最小时WHILE循环的结束，同时也用于暂存待插入元素。 ⑵ 时间上，只包含比较关键字和移动记录两种操作。 ①比较次数 : 1/. 当待初始文件按关键字递增有序(正序)时： a.对每个记录只进行一次比较，整个排序过程共 n 进行了∑1=n-1次比较(最少)； i=2 b.每个记录都要进行r[i]移到r[0]和r[0]移到r[j+1]两次移动，因此共移动2(n-1)次(最少)。 10.2 插入排序 2/. 当待排序文件按关键字非递增有序(逆序)时 ① 记录r[i](i=2,3,...n)均要和前i-1个记录及r[0]进行比较，整个排序过程共进行了 n ∑ i=(n+2)(n-1)/2次比较(最多)； i=2