外部排序:文件中的记录太大，无法全部
将其同时调入内存进行的排序.
排序定义
设有记录序列：{ R1，R2 ， … ，Rn }, 其相应的关键字 序列为：K1, K 2 ,, K n ;
若存在1,2, … ,n的一种排列
1
p1, p2 ,, pn , 使关键字
2 n
非递减（或非递增）： K p K p K;p
插入排序
1.直接插入排序
基本思想：每一次将一个待排序的记录，按其关键字大小插入 到前面已经排好序的有序表中，从而得到一个新的、记录数增 1的有序表。
例: 已知 21、25、22、10、25*、18，用直接插入法将其排序。
0 1 2 3 4 5 6
21
25
22
10
25* 18
直接插入排序过程示例
r 0 1 21 i=2 i=3 i=4 i=5 i=6 22 10 25 18 21 21 21 10 10 10 2 25 25 25 22 15 15 15 3 22 22 22 25 21 21 18 4 10 10 10 10 5 25* 25* 25* 25* 25* 25* 25 6 18 18 18 18 18 18 25*
时间复杂度： T(n)=O(n² )
void binsort(JD r[],int n) { int i,j,x,s,m,k; for(i=2;i<=n;i++) { r[0]=r[i]; x=r[i].key; ‘用择半查找找待插记录的位置 s=1; j=i-1; while(s<=j) { m=(s+j)/2; if(x<r[m].key) j=m-1; else s=m+1; } ‘从i-1 到 s向右移动一个位置 for(k=i-1;k>=s;k--) r[k+1]=r[k]; ‘插入 r[s]=r[0]; } }
3. 2-路插入排序
49 38 65 97 76 13 27 49
当第一个数据在序列 中间位置时，可减少 移动次数，不减少比 较次数。
(49)
(49) (49 65) (49 65 97) (49 65 76 97) (49 65 76 97) (38) (38) (38) (38) (13 38)
i 2
1 n 1
n
记录移动次数：不需移动记录
例如
0
1
2
3
4
5
6
7
13 27 38 49 65 76 97
若待排序记录按关键字从大到小排列(逆序) 关键字比较次数： 记录移动次数：
(n 2)(n 1) i 2 i 2 n (n 4)(n 1) (i 1) 2 i 2
假设待排序的一组记录存放在地址连续的一组存 储单元上。
＃ define MAXSIZE 20 typedef int KeyType； typedef struct { KeyType key; InfoType otherinfo; } RedType; typedef struct { RedType r [MAXSIZE + 1 ] ; // r[0] 空或作哨兵 int length; } SqList;
例
0
i=1
1 2 3 4 5 6 7 (49) 38 65 97 76 13 27
i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27
i=5 76 (38 49 65 76 97) 13 27
Maxint 49 38 65 97 76 13 27 49 2 3 1 4 0
Maxint 49 38 65 97 76 13 27 49 2 3 1 5 0 4
Maxint 49 38 65 97 76 13 27 49 6 3 1 5 0 4 2 Maxint 49 38 65 97 76 13 27 49 6 3 1 5 0 4 7 2 Maxint 49 38 65 97 76 13 27 49 6 8 1 5 0 4 7 2 3
待排记录的数据类型
待排序的记录序列有三种存储方式： 1) 存放在地址连续的一组存储单元上； 2) 存放在静态链表中，记录之间的次序关系由指针指示，则 实现排序不需要移动记录，仅需要修改指针即可； 3) 存储在一组地址连续的存储单元内，同时另设一个指示各 个记录存储位置的地址向量，在排序过程中不移动记录本 身，而移动地址向量中这些记录的“地址”，在排序结束 之后再根据地址向量中的值调整记录的存储位置. 本文假设待排序记录存放在地址连续的一组存储单元上
的记录被安置在第n-1个记录位置；
重复上述过程，直到“在一趟排序过程中没有进行过交换 记录的操作”为止.
例
1 2 3 4
49 38 49 38 65 97 76 97 76 13 13 97 27 27 97 30 30 97
2. 折半插入排序
排序过程： 用折半查找方法确定插入位置的排序
例
i=1 i=2 13
i=7 6 i=8 20 i=8 20
…...
(30) 13 70 85 39 42 6 (13 30) 70 85 39 42 6
(6 (6 s (6 s 13 13 30 30 39 39 42 70 42 70 42 70
交换排序
1. 起泡排序(Bubble Sort)
排序过程
将第一、第二个记录的关键字进行比较，若 r[1].key>r[2].key，则交换；然后比较第二与第三个记 录；依次类推，直至第n-1个和第n个记录比较为止——第
一趟冒泡排序，结果关键字最大的记录被安置在最后一个 记录上；
对前n-1个记录进行第二趟冒泡排序，结果使关键字次大
r[0]的作用? 暂存单元 监视哨
25
25 21
问题1：如何构造初始的有序序列
解决方法： 将第1个记录看成是初始有序表，然后从第2个记录起依次插 入到这个有序表中，直到将第n个记录插入。 算法描述： for (i=2; i<=n; i++) { 插入第i个记录，即第i趟直接插入排序； }
问题2：如何查找待插入记录的插入位置?
0
1
2
3
4
5
Байду номын сангаас
6
7
8
Maxint 49 38 65 97 76 13 27 49 1 0
Maxint 49 38 65 97 76 13 27 49
2 0 1
Maxint 49 38 65 97 76 13 27 49
2
3
1
0
Maxint 49 38 65 97 76 13 27 49 2 3 1 4 0
5. 希尔排序(Shell) (缩小增量法)
排序过程： 先取一个正整数d1<n，把所有相隔d1的记录 放一组，组内进行直接插入排序； 然后取d2<d1，重复上述分组和排序操作； 直至di=1，即所有记录放进一个组中排序为止。
例
初始：
49 38 65 97 76 13 27
48 48
55 55
4 4
20 20
85 ) 20 85 ) 20 j 85 ) 20
m 13 30 39 m
13 13 j j 30 39 s mj 30 39
i=8 20 i=8 20
(6 (6
42 70 42 70
85 ) 20 85 ) 20
s
20 30 39 42 70 85 )
i=8 20
(6
13
算法描述
算法评价
复杂性
O(n2)
(49 65 76 97)
(49 49 65 76 97)
Final
(13 27 38)
(13 27 38)
First
4. 表插入排序
假设数据元素已存储在链表中，且0号单
元作为头结点，不移动记录而只是改变链指针 域，将记录按关键码建为一个有序链表。
首先，将表头结点和数组下标为1的结点构成一个循 环链表，即头结点指针域置1，下标为1结点的链域置 0，并在头结点数据域中存放比所有记录关键码都大 的整数。接下来，逐个结点向链表中插入即可。
n
例如 0 1 2 3 4 5 6 7 97 76 65 49 38 27 13
若待排序记录是随机的，取平均值
2 n 关键字比较次数： 4 2 n 记录移动次数： 4
T(n)=O(n² )
插入排序是一种稳定的排序方法。 原理：关键字相同的两个对象，在整个排 序过程中，不会通过比较而相互交换。
第十章
内部排序
1、插入排序 2、交换排序 3、选择排序 4、归并排序 5、基数排序
概
述
排 序 的 分 类
1. 按排序过程中使用的存储器分 a 内排序 b 外排序
2. 按文件的存储结构分 a 连续顺序文件排序 b 链表排序 3. 按排序的稳定性分 a 稳定性排序 b 不稳定性排序
内部排序:全部记录都可以同时调入内存 进行的排序;
r[0]有两个作用： 1. 进入循环之前暂存了r[i] 的值，使得不致于因记录 的后移而丢失r[i]的内容； 2. 在查找插入位置的循环 中充当哨兵。
整个排序过程为进行n-1趟插入，即先将序列中
第1个记录看成是一个有序子序列，然后从第2个记
录开始，逐个进行插入，直至整个序列有序。
算 法 描 述
typedef struct { int key; float info; }JD; ‘直接插入排序 void straisort(JD r[],int n) { int i,j; for(i=2;i<=n;i++) { r[0]=r[i]; ’哨兵 j=i-1;’从第i-1个位置起，和哨兵分别比较 while(r[0].key<r[j].key) { r[j+1]=r[j]; ’向右移动 j--; } r[j+1]=r[0]; } }