排序的概念与分类

排序于我们的学习生活中随处可见。在列队时，按照个子高矮依次排序；在发布考试成绩时，按照总成绩递减的顺序排列；在制作点名册时，根据姓氏与名字在字母表中的顺序排列。排序是为了方便查找。试想若在一个班级的点名册中查找“赵明”，如果该点名册是无序的，那么需要逐条查阅记录，直到找到“赵明”为止；而若点名册是按照姓名在字母表中的顺序排列的，根据其姓名拼音“zhaoming”中的字母逐层查找，查找的效率就会大大提升。所以，数据排序很有实际意义。

1、排序的定义

对于计算机中存储的数据来说，排序就是将一组“无序”的记录，通过一定的方式，按照某种关键字顺序排列调整为“有序”的记录，从而提高数据查找的效率。

排序的具体定义如下：

假设一组含有n个记录的序列为

{a1,a2,…,an}

每一个记录中相应的关键字分别为

{k1,k2,…,kn}

需确定其下标1,2,…,n的一种排列p1,p2,…,pn，使其相应的关键字满足如下非递减（或非递增）关系

kp1 ≤kp2 ≤ … ≤ kpn

即使序列{a1,a2,…,an}成为一个按关键字有序的序列{rp1,rp2,…,rpn}，这样的操作称为排序。

2、关键字

上述定义中的关键字，可以是记录序列的关键字，也可以是记录序列的次关键字，或者是关键字的组合序列。

假设在一个学生成绩表中有如下两条记录：

表1 成绩表记录示例

一般成绩表都以总分为关键字进行排序，但此时这两位同学的总分相同，所以以姓名的拼音为次关键字，按照拼音中字母在字母表中的顺序来排列。对于“chencheng”和“zhaoyue”中的字母，字母表中“c”在“z”之前，所以在成绩表中将陈诚的成绩记录放在赵越前面。

当然也可以将主关键字和次关键字组合成一个关键字，比如上面的两条记录，将总分和姓名的拼音组合成关键字“188chencheng”和“188zhaoyue”，很容易得到陈诚的“188chencheng”小于赵越的“188zhaoyue”，因此将陈诚排在赵越之前。

3、稳定性

若在原始记录序列中，ai和aj的关键字相同，ai出现在aj之前，经过某种方法排序后，ai的位置仍在aj之前，则称这种排序方法是稳定的；反之，若经过该方法排序后，ai的位置在aj之后，即相同关键字记录的领先关系发生变化，则称这种排序方法是不稳定的。

假设下表中的数据为一个完整的记录序列。

表2 记录序列

以总分为关键字，按照某种排序方法，若排序之后的结果为“章程，林奇，储休，傅娟”，那么该排序算法一定是不稳定的；若排序之后的结果为“章程，储休，林奇，傅娟”，那么排序算法是可能是稳定的。

若要证明一种排序算法是不稳定的，只需举出一个反例说明；若要证明一种算法是稳定的，必须从算法本身的求解步骤进行分析。

4、排序的分类

根据数据存储位置的不同，排序可分为内部排序和外部排序。若所有需要排序的数据都存放在内存中，在内存中调整数据的存储顺序，这样的排序称为内部排序；反之，若待排序记录数据量较大，排序时只有部分数据被调入内存，排序过程中存在多次内、外存之间的交换，这样的排序称为外部排序。

内部排序是排序的基础，根据不同的排序原则，内部排序可分为：交换排序、插入排序、选择排序、归并排序和基数排序五大类。根据算法时间复杂度的差异，这些排序方式又可以有不同的划分。

一般提到的排序算法都是内排序，但是当数据量较大时，内存不能满足排序要求，此时可以选择使用外部排序。外部排序中最常用的算法是多路归并排序，这种算法将源文件分解成多个能够一次性装入内存的子文件，每次把一个或几个子文件调入内存完成排序，最后对已经排序的子文件进行归并排序。

排序算法的实现离不开数据交换，在学习各类算法之前先来实现一个简单的数据交换函数。

//简单数据交换函数
void swap(int *a, int *b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

下面逐一学习这些排序算法。