严蔚敏数据结构第九章.pptx

第10章 内部排序;10.1 排序的基本概念; ◆ Ki是主关键字：排序后得到的结果是唯一的； ◆ Ki是次关键字：排序后得到的结果是不唯一的。 ⑵ 排序的稳定性 若记录序列中有两个或两个以上关键字相等的记录： Ki =Kj(i≠j，i, j=1, 2, … n)，且在排序前Ri先于Rj(ij)，排序后的记录序列仍然是Ri先于Rj，称排序方法是稳定的，否则是不稳定的。 排序算法有许多，但就全面性能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。 评价排序算法的标准有：执行时间和所需的辅助空间，其次是算法的稳定性。; 若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是O(1) ，则称排序方法是就地排序，否则是非就地排序。 ⑶ 排序的分类 待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。 ① 待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序； ② 待排序的记录数太多：所有的记录不可能存放在内存中， 排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。;⑷ 内部排序的基本操作 对内部排序地而言，其基本操作有两种： ◆ 比较两个关键字的大小； ◆ 存储位置的移动：从一个位置移到另一个位置。 第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是： ① 记录存储在一组连续地址的存储空间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必不可少的； ② 记录采用链式存储方式：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不需要移动记录；;③ 记录存储在一组连续地址的存储空间：构造另一个辅助表来保存各个记录的存放地址(指针) ：排序过程不需要移动记录，而仅需修改辅助表中的指针，排序后视具体情况决定是否调整记录的存储位置。 ①比较适合记录数较少的情况；而②、③则适合记录数较少的情况。 为讨论方便，假设待排序的记录是以①的情况存储，且设排序是按升序排列的；关键字是一些可直接用比较运算符进行比较的类型。;待排序的记录类型的定义如下： #define MAX_SIZE 100 Typedef int KeyType ; typedef struct RecType { KeyType key ; /* 关键字码 */ infoType otherinfo ; /* 其他域 */ }RecType ; typedef struct Sqlist { RecType R[MAX_SIZE] ; int length ; }Sqlist ;;10.2 插入排序;10.2.1 直接插入排序; 例：设有关键字序列为：7, 4, -2, 19, 13, 6，直接插入排序的过程如下图10-1所示：;2 算法实现 void straight_insert_sort(Sqlist *L) { int i, j ; for (i=2; i=L-length; i++) { L-R[0]=L-R[i]; j=i-1; /* 设置哨兵 */ while( LT(L-R[0].key, L-R[j].key) ) { L-R[j+1]=L-R[j]; j--; } /* 查找插入位置 */ L-R[j+1]=L-R[0]; /* 插入到相应位置 */ } };3 算法说明 算法中的R[0]开始时并不存放任何待排序的记录，引入的作用主要有两个： ① 不需要增加辅助空间： 保存当前待插入的记录R[i]，R[i]会因为记录的后移而被占用； ② 保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记录，起“哨兵监视”作用，避免在内循环中每次都要判断j是否越界。;4 算法分析 ⑴ 最好情况：若待排序记录按关键字从小到大排列(正序)，算法中的内循环无须执行，则一趟排序时：关键字比较次数1次，记录移动次数2次(R[i]→R[0], R[0]→R[j+1])。 则整个排序的关键字比较次数和记录移动次数分别是：;⑵ 最坏情况：若待排序记录按关键字从大到小排列(逆序)，则一趟排序时：算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。 则就整个排序而言：;10.2.2 其它插入排序;low=1 ; high=i-1