|
基本概念 关键字项及关键字（Key）记录由若干个数据项（或域）组成其中有一项可用来标识一个记录称为关键字项该数据项的值称为关键字 排序（Sorting）又称分类假设含 n 个记录的序列为{RR…Rn}其相应的关键字序列为{KK…Kn} 需确定…n的一种排列pp…pn使其相应的关键字满足如下的非递减（或非递增）关系 Kp≤Kp≤…≤Kpn 即使初始的的序列成为一个按关键字有序的序列{RpRp…Rpn}这样一种操作称为排序 如果待排序的文件中存在有多个关键字相同的记录经过排序后这些具有相同关键字的记录之间的相对次序保持不变则称这些排序方法是稳定的反之则称这种排序方法是不稳定的 排序算法的稳定性是针对所有输入实例而言的即在所有可能的输入实例中只要有一个实例使得算法不满足稳定性要求则该排序算法就是不稳定的 排序方法 ①内部排序 内部排序（Internal Sorting）在排序过程中若整个文件都是放在内存中处理排序时不涉及数据的内外存交换则称之为内排序 按所用的策略不同内部排序方法可以分为五类插入排序选择排序交换排序归并排序分配排序 ②外部排序 外部排序（External Sorting）若排序过程中要进行数据的内外存交换则称之为外部排序 排序过程的基本操作 ①比较两个关键字的大小 ②改变指向记录的指针或移动记录本身 评价排序算法好坏的标准执行时间和所需的辅助空间另外算法本身的复杂程度也是要考虑的一个因素 就地排序（InPlace Sort）若排序算法所需的辅助空间并不依赖于总是的规模n也就是说辅助空间是O()则称之为就地排序 顺序表类型说明 几种基本的排序方法 |
