数据结构精品课件-排序的基本概念和插入类排序.pptVIP

* * * * * * * * * * * * * * * * * * * * * 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序法 9.4 选择类排序法 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的综合比较 第九章 内部排序 9.8 总结与提高 一、排序的定义 　 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 例如：将如下序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 9.1 排序的基本概念 设含 n 个记录的序列为 { R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 记录关键字相互之间可以进行比较，即存在关系 ： Kp1≤Kp2≤…≤Kpn 按此关系将上述记录序列调整为 { Rp1, Rp2, …，Rpn } 的操作称作排序。 定义： 设待排序记录序列中有关键字相等的记录, 即ki=kj(ij), 且在排序前Ri领先于Rj. 若排序后可以保证Ri仍领先于Rj, 则所用的排序方法称为稳定的; 若排序后不能保证Ri仍领先于Rj, 则所用的排序方法称为不稳定的. 二、稳定的排序和不稳定的排序 例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后必有结果： ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的; 若排序后可能得结果： ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。 　 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。 反之, 若参加排序的记录数量很大, 整个序列的排序过程不可能在内存 中完成，则称此类排序问题为外部排序。 三、内部排序和外部排序 1、顺序存储：移动记录实现排序； 2、(静态)链表：修改指针(游标)实 现排序； 3、地址向量：移动地址实现排序； (又称地址排序) 四、内部排序的存储方式 本课程我们重点讨论在顺序存储结构上，各种排序方法的实现。 返回 9.2 插入类排序 　 将无序序列中的记录一个一个的 “插入”到有序序列中的恰当位置，以逐渐增加有序序列的长度K(K=1 N), 从而实现排序。 基本思想： 有序序列r[1..i-1] r[i] 无序序列 r[i..n] 有序序列r[1..i] 无序序列 r[i+1..n] 找位置 插入 一趟插入排序的基本过程： 实现“一趟插入排序”可分三步进行： 3．插入：将r[i] 插入(复制)到r[j+1]的位置上。 2．后移：将r[j+1..i-1]中的所有记录均后移一个位置； 1．查找插入位置：在r[1..i-1]中查找r[i]的插入位置j+1 ： r[1..j].key ? r[i].key r[j+1..i-1].key； 直接插入排序（基于顺序查找） 不同的具体实现方法导致不同的算法描述 折半插入排序（基于折半查找） 希尔排序（基于逐趟缩小增量） 　　利用 “顺序查找”实现 “在r[1..i-1]中查找r[i]的插入位置” 算法的实现： 一、直接插入排序 1. 从r[i-1]起向前进行顺序查找， 循环结束确定r[i]的插入位置为 j +1; r[0] j r[i] j=i-1 插入位置 2. 将所有 j+1…i-1 的记录向后移动 1位; j j j 3. 将r[0](原r[i])“插入”到j+1的位置。 监视哨设置在r[0]； 可以在查找的同时实现记录向后移动； r[0]=r[i]; j=i-1; while( r[0].key r[j].key) { r[j+1]= r[j]; j=j-1;} r[0] j r[i] j= i-1 上述循环结束后可以直接进行“插入” 插入位置 方法的改进: 令 i = 2,3,…, n, 可实现整个序列的排序。 Void inssort(recordtype r[ ], int n) {for（i=2;i=n; i++) {r[0]=r[i]; j=i-1; while(r[0].key r[j].key) { r[j+1]= r[j];