学科分类
目录
数据结构

排序的概念与分类

排序于我们的学习生活中随处可见。在列队时,按照个子高矮依次排序;在发布考试成绩时,按照总成绩递减的顺序排列;在制作点名册时,根据姓氏与名字在字母表中的顺序排列。排序是为了方便查找。试想若在一个班级的点名册中查找“赵明”,如果该点名册是无序的,那么需要逐条查阅记录,直到找到“赵明”为止;而若点名册是按照姓名在字母表中的顺序排列的,根据其姓名拼音“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 成绩表记录示例

姓名 语文 数学 总分 名次
陈诚 95 93 188 5
赵越 94 94 188 5

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

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

3、稳定性

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

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

表2 记录序列

姓名 语文 数学 总分
储休 95 93 188
林奇 94 94 188
章程 97 99 196
傅娟 90 96 186

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

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

4、排序的分类

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

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

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

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

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

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

点击此处
隐藏目录