1、第 10章 内部排序1. 排序的基本概念l排序 :将一组杂乱无章的数据按一定的规律顺次排列起来，使之按关键字递增 (或递减 )有序排列。3 10 5 78 363 5 10 36 78排序 : 设 n 个记录的序列为 R1 , R2 , R3 , . . . , Rn 其相应的关键字序列为 K1 , K2 , K3 , . . . , Kn 若规定 1 , 2 , 3 , . . . , n 的一个排列 p1 , p2 , p3 , . . . , pn ，使得相应的关键字满足如下非递减关系 :Kp Kp Kp . . . Kp1 2 3 n则原序列变为一个按关键字有序的序列 :Rp , Rp
2、 , Rp , . . . , Rp1 2 3 n 此操作过程称为 排序 。稳定排序 与 不稳定排序假设 Ki = Kj ，且排序前序列中 Ri 领先于 Rj ；若在排序后的序列中 Ri 仍领先于 Rj ，则称排序方法是稳定的 。若在排序后的序列中 Rj 领先于 Ri ，则称排序方法是 不稳定的 。例，序列 3 15 8 8 6 9若排序后得 3 6 8 8 9 15 稳定的若排序后得 3 6 8 8 9 15 不稳定的排序的时间开销 ：算法执行中 关键字比较次数 和 记录移动次数 来衡量。对于那些受关键字序列初始排列及记录个数影响较大的，需要按最好情况和最坏情况进行估算。内部排序 与 外部排
3、序内部排序 : 指的是待排序记录存放在计算机 随机存储器中进行的排序过程。外部排序 : 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对 外存 进行访问的排序过程。l 排序方法分类排序内部排序外部排序涉及存储器不同策略 ( 原则 )不同工作量不同 插入排序 交换排序 选择排序 归并排序 计数排序 简单的排序方法 先进的排序方法 基数排序l待排序的顺序表类型的类型定义#define MAXSIZE 20 /表长typedef int KeyType; /关键字类型typedef struct KeyType key; /关键字项InfoType otherType;
4、/其它数据项 RecType; /记录类型typedef structRecType rMAXSIZE+1; /r0哨兵单元int length;SqList;10.2 插入排序插入排序 (Insertion Sort)的基本思想是：每次将一个待排序的记录 ,按其关键字大小插入到前面已经排好序的子表中的适当位置 ,直到全部记录插入完成为止。5种插入排序方法：(1) 直接插入排序 ;(2) 折半插入排序 ;(3) 2-路插入排序 ;(4) 表插入排序 ;(5) 希尔排序。10.2.1 直接插入排序思想 : 利用有序表的插入操作进行排序有序表的插入 : 将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。例，序列 13 27 38 65 76 97 插入 4913 27 38 49 65 76 97例，序列 49 38 65 97 76 13 27 初始， S = 49 ； 38 49 算法描述 :初始，令第 1 个元素作为初始有序表；依次插入第 2 , 3 , , k 个元素构造新的有序表；直至最后一个元素； 38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要应用 比较 和 移动 两种操作。
