摘要：计算机科学是一门研究数据表示和数据处理的科学。数据就是对客观事务采用的计算机能够识别、存储和处理的符号表示。简言之，数据是计算机化的信息，是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制，还是对文件的存储和检索等计算机应用，都是对数据进行加工处理的过程。计算机对数据的处理并不是简单地将数据堆积在一起，而是使其具有某种内在的联系。因此，为了更有效地处理数据，设计出好的算法，编写出结构清晰而且效率高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。所谓排序（sorting）,就是指将一组记录的任意序列按规定顺序重新排列。排序的目的是便于查询和处理，提高解决问题的效率。它是计算机数据处理的一种重要的操作，如字典是典型的排序结构，将字或词按字母顺序排列，便于查询。排序的确切定义：假设含n个记录的排序为｛R1,R2,…,Rn｝,其相应的关键安序列为｛K1,K1,…,Kn｝,需要确定1,2,…,n的一种排列p1,p2,…,pn,使其相应的关键字满足如下的非递减（或非递增）关系：Kp1<=Kp2<=…<=Kpn。即使｛R1,R2,…,Rn｝的一个序列成为一个关键字有序序列｛Kp1,Kp2,…,Kpn｝这样一处操作称为排序。换句话说，排序就是要重排一组记录，使其关键字域的值具有非递减或非递增的顺序，经过排序的数据若其关键字值从小到大的顺序，称为升序，反之称为降序。上述定义记录中的关键字Ki可以是记录的主关键字，也可以是次关键字，甚至是若干数据项的组合。主关键字，在记录序列中关键字值互不相等，该记录序列经排序过后，得到唯一的结果。例如，在一个学生信息记录中，学号即为主关键字。次关键字是指待排序的记录序列中可能存在两个或两个以上关键字相等，则排序的结果不唯一。例如，学生记录中的成绩可看成次关键字。假设Ki=Kj(1<=i<=n,1<=j<=n,i!=j),且在排序前的序列中Ri领先于Rj，则称所用的排序方法是稳定的，反之，若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。

作者：张伟深   班级：计算机应用与维护   点击下载