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