第一节 - 基本概念
发布时间：2020-09-20 11:05来源：未知
第一节 基本概念
1、排序（sort）的概念
所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。
2、排序的稳定性
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
注意：
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
3、排序方法的分类
（1）按是否涉及数据的内、外存交换分
在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。
注意：
① 内排序适用于记录个数不很多的小文件
② 外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。
（2）按策略划分内部排序方法
内部排序可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
4．排序算法性能评价
（1）评价排序算法好坏的标准
① 执行算法需要的时间
② 算法所需的辅助空间
③ 算法本身的复杂程度
（2）排序算法的时间开销
一般情况下，用算法执行中关键字之间的比较次数和记录的移动次数来衡量。
（3）排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n，空间复杂度是O(1)，则称这样的排序为就地排序。非就地排序的空间复杂度是一般为O(n)。
5、待排序记录的数据类型定义
#define n l00 //假设的文件长度，即待排序的记录数目
typedef int KeyType； //假设的关键字类型
typedef struct //记录类型
{ KeyType key； //关键字项
InfoType otherinfo； //其它数据项，类型InfoType依赖于具体应用而定义
}RecType；
typedef RecType SeqList[MAXSIZE+1]；
//SeqList为顺序表类型，表中第0个单元一般用作哨兵
sqlist R； //R 顺序表类型数组
【真题选解】
（例题•单选题）如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( )
A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的
