排序 排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继
设 R 为非空集合A 上的二元关系，如果R 满足自反性(对于每一个x∈ A， (x,x)∈ R )， 反对称性((x,y)∈ R∧ (y,x)∈ R→ x=y )和传递性((x,y)∈ R∧ (y,x)∈ R→ (x,z)∈ R)，则称R 为 A 上的偏序关系，记作≤
如果(x,y)∈ R，则记作x≤y，读作“x小于等于y”
存在偏序关系的集合A 称为偏序集
注意，这里的≤不是指数的大小，而是指在偏序关系中的顺序性
x≤y的含义是：按照这个序，x 排在y前面
根据不同的偏序定义，≤有不同的解释
例如整除关系是偏序关系≤，3≤6的含义是3 整除6
大于或等于关系也是偏序关系，针对这个关系5≤4 是指在大于或等于关系中5 排在4 的前面，也就是说5 比4 大
在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的
在该记录类型中有一个主键域key， key 域的类型是某一个偏序集，记录的其他域称为卫星数据
比较线性表中的两个元素Li 和Lj 的大小，实际上是比较Li
key 和 Lj
key 的大小（这种比较当然也是偏序集中的比较）
举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为key 域对员工记录排序，则是将员工记录按照编号排序；如果以工资为key 域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为key 域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序
关于偏序集的具体概念和应用，请参见离散数学的相关资料
如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法(in
