文档介绍：第十章内部排序
1、概述 2、插入排序 3、交换排序 4、选择排序 5、归并排序 6、基数排序
1
排序的分类:
内部排序:全部记录都可以同时调入内存进行的排序。
外部排序:文件中的记录太多,无法全部将其同时调入内存进行的排序。
1、概述
2
定义:设有记录序列:{ R1、R2 ……….. Rn }
其相应的关键字序列为: { K1、K2 ……….. Kn };
若存在一种确定的关系: Kx <= Ky <= …<= Kz
则将记录序列{ R1、R2 ……….. Rn } 排成按该关键字有序的
序列{ Rx、Ry ……….. Rz } 的操作,称之为排序。
关系是任意的,如通常使用的小于、大于等关系。
稳定与不稳定:若记录序列中的任意两个记录 Rx、Ry 的关键字 Kx = Ky ;
如果在排序之前和排序之后,它们的相对位置保持不变,
则这种排序方法是稳定的,否则是不稳定的。
3
# define MAXSIZE 20
typedef int KeyType;
typedef struct {
KeyType key;
InfoType otherinfo;
} RedType;
typedef struct {
RedType r [MAXSIZE + 1 ] ; // r[0] 空或作哨兵
int length;
} SqList;
4
r[0] 用作哨兵。共执行 5 遍操作。
每遍操作:先将元素复制内容放入r[0],再将本元素同已排序的序列,从尾开始进行比较。在已排序的序列中寻找自己的位置,进行插入。或者寻找不到,则一直进行到哨兵为止。意味着本元素最小,应该放在 r[1] 。
每一遍,排序的序列将增加一个元素。如果序列中有 n 个元素,那么最多进行n 遍即可。
2、插入排序
例:36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中,用直接插入法将其排序。结果仍保存在下标为 1 至 5 的元素之中。
直接插入排序
0
1
2
36
24
10
6
12
3
4
5
5
0
1
2
36
24
10
6
12
3
4
5
36
24
24
i
6
0
1
2
36
24
10
6
12
3
4
5
36
24
i
7
0
1
2
36
24
10
6
12
3
4
5
36
24
i
24
8
0
1
2
36
24
10
6
12
3
4
5
36
10
i
24
10
9
0
1
2
36
24
10
6
12
3
4
5
36
10
i
24
10