排序的基本概念

9.1　排序的基本概念

1.排序的定义

排序就是把一组无序的数据（记录）序列按关键字重新排列成有序序列的过程。换句话说,排序就是重排一组记录,使其按关键字具有递增（或递减）的顺序。本章所讲的排序默认为按关键字非递减的顺序排序。排序的具体定义如下。

设有一组包含n个记录的序列为:{R₁,R₂,R₃,…,R_n},其对应的关键字序列为:{K₁,K₂,K₃,…,K_n}；则对于1,2,3,…,n,存在一种确定的排列p₁,p₂,p₃,…,p_n,使得关键字序列{K₁,K₂,K₃,…,K_n}满足条件:K_p1≤K_p2≤…≤K_pn（非递减）或者K_p1≥K_p2≥…≥K_pn（非递增）,此时获得的记录序列R_p1,R_p2,…,R_pn即是按照关键字排序的序列,获得该序列的这一操作过程就称为排序。

例如,设有记录的序列,其关键字值为:（K₀,K₁,K₂,K₃）＝（35,26,81,40）,排序运算是求（p（0）,p（1）,p（2）,p（3））,使得（K_p（0）≤K_p（1）≤K_p（2）≤K_p（3））。其结果应为:（p（0）,p（1）,p（2）,p（3））＝（1,0,3,2）。此时有（K₁,K₀,K₃,K₂）＝（16,25,30,71）,它是按关键字值递增的有序序列。

2.排序的稳定性

根据关键字相同的记录排序前后相对位置的关系,排序可以分为稳定排序和不稳定排序两种。在待排序序列之中如果存在两个记录R_i和R_j,其对应的关键字分别是K_i和K_j,其中i≤j且K_i＝K_j,即排序前记录R_i在记录R_j之前。排序完成之后,如果记录R_i和R_j的相对位置不发生改变,这种排序称为稳定排序；反之,如果记录R_i和R_j的相对位置发生了改变,则称这种排序为不稳定排序。

3.内排序和外排序

根据排序过程所涉及的存储介质的不同,排序可分为内部排序和外部排序两种。内部排序是指待排的记录全部在内存中完成排序的过程,内部排序也称为内排序。若待排序记录的数量庞大,在排序的过程中需要使用到外部存储介质如磁盘等,这种涉及内外存储器数据交换的排序过程称为外部排序,又称为外排序。内排序是外排序的基础,外排序算法的原理和内排序算法的原理在很多方面都类似,但因内存的读写速度与外存的读写速度存在很大差别,因而实际操作中仍有不同。本章主要介绍内排序。

内排序的方法很多,依照排序所采用方式的不同,可分为插入排序、交换排序、选择排序、归并排序和基数排序等多种排序方法。这些排序方法都有其自身的优缺点,在实际中要根据具体情况进行合理选择,编写出效率较高的排序方法。

排序过程实际上就是将无序的记录序列通过记录关键字的比较和记录的位置移动,使序列变成按照关键字有序的序列,因此内排序过程中有以下两种基本操作:①比较两个关键字的大小；②将记录从一个位置移动至另一个位置。第一种操作对大多数排序方法来说都是必须的,第二种操作则要看记录序列的存储方式。对于顺序存储方式的记录序列需要发生记录的移动,而对于链式存储结构的序列则不需要发生记录的移动。本章所介绍内排序算法中的记录采用的存储方式均为顺序结构存储方式,即数组存储方式。

对某一个待排序序列,可以采用多种不同的排序算法进行排序,判断到底哪种排序算法更好,通常采用如下两条标准来衡量算法优劣。

（1）时间复杂度　时间复杂度是衡量排序算法好坏的最重要的标准。本章所介绍内排序算法的时间复杂度采用关键字比较的次数和记录移动的次数来衡量,亦可使用平均时间复杂度来进行估算。

（2）空间复杂度　空间复杂度也是衡量排序算法好坏的一个重要标准,它用于衡量使用的辅助内存空间的多少。当排序算法中使用的辅助内存空间与要排序数据元素个数n无关时,其空间复杂度为O（1）,大多数排序算法的空间复杂度都是O（1）。

在本章中,若无特别说明,均假定待排序的记录序列采用一个顺序表结构来存储,并且假定是按关键字的递增（或非递减）序排序。在后面所学的各种排序算法中,均将排序记录的数据结构定义如下。

为了简单起见,上述结构直接假设记录的关键字为整型数据。在实际应用中,若关键字的类型没有可直接使用的比较运算符,则可事先定义宏或函数来完成比较运算。