T9（一）-基本概念和插入类排序.ppt

比较 见课本P305面表9－2，表9－3 46 55 42 94 17 0 1 2 3 4 5 6　　7　　8 05 70 i i=8 13 致此，序列已基本排好序 不稳定的排序算法！ 逆转数： 对于待排序序列中的某个记录的关键字，它的逆转数是指在它之前比此关键字大的关键字个数。 算法分析： 时间复杂度： 算法分析： 第九章　 排序 排序的基本概念 插入类排序 交换类排序法 选择类排序法 归并排序 各种排序方法的综合比较 总结与提高 本章目标 9.1 排序的基本概念 排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 内部排序 外部排序 内部排序：整个排序过程完全在内存中进行，称为内部排序。 外部排序：由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。 假设Ki是Ri 的主关键字，Kj是Rj 的主关键字， 稳定排序：若Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，在排序前的序列中Ri领先于Rj(即ij)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的 ； 不稳定排序：反之，当相同关键字的领先关系在排序过程中发生变化者，则称所用的排序方法是不稳定的。 在排序过程中，一般进行两种基本操作： （1）比较两个关键字的大小； （2）将记录从一个位置移动到另一个位置。 对于第二种操作，需要采用适当地存储方式， 向量结构 链表结构 记录向量与地址向量结合的表示方法 我们重点来讨论在向量存储结构上各种排序方法的实现。 9.2 插入类排序 基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。 直接插入排序 折半插入排序 希尔排序　 9.2.1 直接插入排序 基本操作：将第i个记录插入到前面i-1个已排好序的记录中， 具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，…K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。 21 25 49 25* 16 08 0 1 2 3 4 5 6 0 1 2 3 4 5　　6 21 49 25* 16 08 i = 2 0 1 2 3 4 5 6 21 25 25* 16 08 i = 3 无序数组 ＞ 49 ＞ 监 视 哨 25 25 25* 21 25 49 16 08 0 1 2 3 4 5　　6 0 1 2 3 4 5 6 21 25 49 25* 16 08 i = 5 0 1 2 3 4 5 6 21 25 49 25* 16 08 i = 6 i = 4 16 08 = { 48 } 62 35 77 55 14 35 98 { 48 62 } 35 77 55 14 35 98 { 35 48 62 } 77 55 14 35 98 { 35 48 62 77 } 55 14 35 98 { 35 48 55 62 77 } 14 35 98 { 14 35 48 55 62 77 } 35 98 { 14 35 35 48 55 62 77 } 98 {