例子，该例中两个相同关键字在排序前后的相对次序发生了变化。选择排序选择排序也是种简单排序法。个记录最多只需进行次交换就可以直接到达它的排序位置。设待排序的文件为进行选择排序的基本步骤如下置为当时，重复下列步骤当中选出个关键字最小的记录，若不是，即则交换和的位置否则，不进行交换。的值加。第遍扫描时，在个记录中为了选出最小关键字的记录，需要进行次比较，第扫描时，在余下的记录中，再选出具有最小关键字的记录需要比较次，第扫描时，在最后的个记录中，比较次选出最小关键字的记录。堆排序堆排序是在选择排序的基础上发展起来的。它比选择排序的效率要高。在堆排序中，把待排序的文件逻辑上看作是棵顺序二叉树，并用到堆的概念。在介绍堆排序之前，先引入堆的概念。我们回忆下，棵有个结点的顺序二叉树可以用个长度为的向量维数组来表示反过来，个有个记录的顺序表示的文件，在概念上可以看作是棵有个结点即记录的顺序二叉树。例如，个顺序表示的文件可以看作为图所示的顺序二叉树。当我们把顺序表示的文件，看作为顺序二叉树时，由顺序二叉树的性质可知记录，则的左孩子不存在的右孩子是记录，但若，则的右孩子不存在。什么是堆呢堆是个具有这样性质的顺序二叉树，每个非终端结点记录的关键字大于等于它的孩子结点的关键字。例如，图所示的顺序二叉树就是个堆。显然，在个堆中，根结点具有最大值指关键字，下同，而且堆中任何个结点的非空左右子树都是个堆，它的根结点到任叶子的每条路径上的结点都是递减有序的。堆排序的基本思想是首先把待排序的顺序表示维数组的文件，在概念上看作棵顺序二叉树，并将它转换成个堆。这时，根结点具有最大值，删去根结点，然后将剩下的结点重新调整为个堆。反复进行下去，直到只剩下个结点为止。堆排序的关键步骤是如何把棵顺序二叉树调整为个堆。初始状态时，结点是随机排列的，需要经过多次调整才能把它转换成个堆，这个堆叫做初始堆。建成堆之后，交换根结点和堆的最后个结点的位置，相当于删去了根结点。同时，剩下的结点除原堆中的根结点又构成棵顺序二叉树。这时，根结点的左右子树显然仍都是个堆，它们的根结点具有最大值除上面删去的原堆中的根结点。把这样棵左右子树均是堆的顺序二叉树调整为新堆，是很容易实现的。例如，对于图所示的堆，交换根结点和最后的结点之后，便得到图所示的顺序二叉树除之外。现在，新的根结点是，其左右子树仍然都是堆。下面讨论如何把这棵二叉树调整为个新堆。由于堆的根结点应该是具有最大值的结点，且已知左右子树是堆，因此，新堆的根结点应该是这棵二叉树的根结点，根结点的左孩子，根结点的右孩子若存在的话中最大的那个结点。于是，先找出根结点的左右孩子，比较它们的大小。将其中较大的孩子再与根结点比较大小。如果这个孩子大于根结点，则将这个孩子上移到根结点的位置，而根结点下沉到这个孩子的位置，即交换它们的位置。在图中，根结点的左右孩子分别是，由于，并且，于应的队列中个位数为的关键字，其记录依次放入号队列中个位数为的关键字，其记录放入号队列中个位数为的关键字，其记录放入号队列中。这过程叫做按个位数分配。现在把这个队列中的记录，按号，号，号队列的顺序收集和排列起来，同队列中的记录按先进先出的次序排列。这是第遍。第遍排序使用同样的办法，将第遍排序后的记录按其关键字的十位数第位分配到相应的队列中，再把队列中的记录收集和排列起来。继续进行下去。第遍排序时，按第遍排序后记录的关键字的最高位第位进行分配，再收集和排列各队列中的记录，医得到了原文件的有序文件，这就是以为基的关键字的基数排序法。关键字初始状态个队列关键字第遍，按个位数分配收集后收集后第二遍，按十位数分配例如，给出关键字序列其中关键字用个在的前面补足到位，余关键字均为位的正整数。进行基数排序的过程如图所示。在这个例子中，文件和所有的队列都表示成向量维数组。显然，关键字的位有可能均为同个数字例如，个数都为，这时所有的记录都同时装入同个队列中例如，同时装入号队列中。因此，如果每个队列的大小和文件大小相同，则需要个倍于文件大小的附加空间。此外，排序时需要进行反复的分配和收集记录。所以，采用顺序表示是不方便的。基数排序所需的计算时间不仅与文件的大小有关，而且还与关键字的位数关键字的基有关。设关键字的基为十进制数的基为，二进制数的基为，为建立个空队列所需的时间为。把个记录分放到各个队列中并重新收集起来所需的时间为，因此遍排序所需的时间为。若每个关键字有位，则总共要进行遍排，所以基数排序的时间复杂度为。由于关键字的位数直接与基数以及最大关键字的值有关，因此不同的和关键字将需要不同的时间。在已介绍的上述各种内部排序方法中，就所需要的计算时间来看，快速排序归并排序堆排序是很好的方法。但是，归并排序需要大小为的辅助空间，快速排序需要个栈空。除了快速排序堆排序选择排序不稳定外，基它排序方法都是稳定的。评价个排序算法性能好坏的主要标准是它所需的计算时间和存储空间。影响计算时间的两个景要因素是比较关键字的次数和记录的移动次数。在实际应用中，究竟应该选用何种排序方法，取决于具体的应用和机器条件。外部排序外部排序基本上由两个相对的阶段组成。首先，按可用内存大小，将外存上含个记录的文件分成若干长度为的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串然后，对这些归并段进行逐趟归并，使归并段有序的子文件逐渐由小至大，直至得到整个有序文件为止。显然，第阶段的工作是上章已经讨论过的内容。本章主要讨论第二阶段即归并的过程。先从个具体例子来看外排中的归并是如何进行的假设有个含个记录的文件，首先通过次内部排序得到个初始归并段，其中每段都含个记录。然后对它们作如下图所示的两两归并，直至得到个有序文件为止。将两个有序段归并成个有序段的过程，若在内存进行，则很简单，上章中的过程便可实现此归并。但是，在外部排序中实现两两归并时，不仅要调用过程，而且要进行外存的读写，这是由于我们不可能将两个有序段及归并结果段同时存放在内存中的缘故。在节中已经提到，对外存上信息的读写是以“物理块”为单位的。假设在上例中每个物理块可以容纳个记录，则每趟归并需进行次“读”和次“写”，四趟归并加上内部排序时所需进行的读写使得在外排中总共需进行次的读写。般情况下，外部排序所需总的时间内部排序产生初始归并段所需的时间外部信息读写的时间内部归并所需的时间其中是为得到个初始归并段进行内部排序所需时间的均值是进行次外存读写时间的均值是对个记录进行内部归并所需时间为经过内部排序之后得到的初始归并段的个数为归并的趟数为总的读写次数。其中取决于所用的外部设备，显然，较要大得多。因此，提高外排的效率应主要着眼于减少外存信息读写的次数。下面来分析和“归并过程”的关系。若对上例中所得的个初始归并段进行路平衡归并即每趟将个或个以下的有序子文件归并成个有序子文件，则从下图可见，仅需进行二趟归并，外排时总的读写次数便减至，比路归并减少了次的读写。└┴┴┘└┴┴┘ˊˊ└┬┘有序文件可见，对同文件而言，进行外排时所需读写外存的次数和归并的趟数成正比。而在般情况下，对个初始归并段进行路平衡归并时，归并的趟数可见，若增加或减少便能减少。各种排序方法的比较迄今为止，已有的排序方法远远不止本章讨论的这些方法，人们之所以热衷于研究多种排序方法，不仅是由于排序在计算机中所处的重要地位，而且还因为不同的方法各有其优缺点，可适用于不同的场合。选取排序方法时需要考虑的因素有待排序的记录数目记录本身信息量的大小关键字的结构及分布情况对排序稳定性的要求语言工具的条件，辅助空间的大小等。依据这些因素，可得出如下几点结论若较小譬如，可采用直接插入排序或直接选。由于直接插入排序所需记录移动操作较直接选择排序多，因此若记录本身信息量较大时，则选用直接选择排序为宜。若文件的初始状态已是按关键字基本有序，则选用直接插入排序泡排序为宜。若较大，则应采用时间复杂度为的排序方法快速排序堆排序或归并排序，快速排序是目前基于内部排序的中被认为是最好的方法，档待排序的关键字是随机人布时，快速排序的平均时间最少，但堆排序所需的辅助窨少于快速排序，并且不会出现序可能出现的最坏情况，这两种排序方法都是不稳定的，若要求排序稳定则可选用归并排序。但本文章结合介绍的单个记录起进行两两归并排算法并不值得提倡，通常可以将它和直接排序结合在起用。先利用直接插入排序求得的子文件，然后，再两两归并之。因为直接插入排序是稳定的，所以，改进后的归并排序是稳定的。在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此，可以利用棵二叉树来描述比较判定过程，由此可以证明当文件的个关键字分布时，任何借助于比较的排序算法，至少要的时间，由于箱排序和基数排序只需步就会引起种可能的转移，即把个记录半装入个箱子之，因此，在般情况下，箱乔序和排序可能在时间内完成对个记录的。但踞的是，箱排序和排序只适用于象字符串和整数这类有明显的结构特征的关键字，当关键字的取值范围属于个无穷集合时，无法使用箱排序和排序，这时只有借助于比较方法来排序。由此可知，若较大，记录的关键字倍数较少时且可以分解时采用排序较好。前面讨论的排序算法，除排序外，都是在维数组上实现的，当记录本身信息量较大时，为了避免浪费大量时间移动记录，可以用链表作为存储结构，如插入排序和归并排序都易于在链表上实现，并分别称之为表和归并表，但有的方法，如快速排序和堆排序，在链表上难于实现，在这种情况下，可以提取关键字建立索引表，然后，对索引表进行排序。然而更为简单的方法是引入个整形向量作为辅助表，排序前，若排序算法中要求交换，则只需交换和即可，排序结束后，向量就指示了记录之间的顺序关系无论是用链表还是用辅助窨来实现排序，都有可能要求最终结果是若上述要求，则可以在排序结束后，再按链表或辅助窨表所规定的次序重排各记录，完成这种重排时间是。本章小结排序是计算机程序设计中的种重要操作，它的功能是将个数据元素或记录的任意序列，重新排列成个按关键字有序的序列。本章主要介绍了排序的概念及其基本思想，排序过程和实现算法，简述了各种算法的时间复杂度和空间复杂度。个好的排序算法所需要的比较次数和存储空间都应该较少，但从本章讨论的各种排序算法中可以看到，不存在“十全十美”的排序算法，各种方法各有优缺点，可适用于不同的场合。由于排序运算在计算机应用问题中经常碰到，读者应重点理解各种排序算法的基本思想，熟悉过程及实现算法，以及对算法的分析方法，从而面对实际问题时能选择合适的算法。排序排序是计算机程序设计中的种重要操作，它的功能是将个数据元素或记录的任意序列，重新排列成个按关键字有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类类是内部排序，指的是待排序