顺序存储的线性表中关键字数量有限的记录的排序方法

摘 要 关于排序已经有许多成熟的算法，但对于一些特殊的问题和有特殊要求的问题，已有的一些经典的排序算法却不一定能满足题目要求，本文就关键字数量有限的记录的排序问题提出了一个有效的算法。 关键词 排序；关键字；比较；交换 1 引言 排序是计算机程序设计中的一种重要操作，它的功能是将一个或记录的任意序列重新按其关键字的某种次序(非递减或非递增顺序)排列起来，使其具有一定的顺序，以便于进行数据查找。通常，在排序过程中需进行下列两种基本操作：①比较两个关键字的大小；②将记录从一个位置移动到另一个位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作则随着记录的存储方式和使用的排序方法的不同而有所不同。对于存储在线性表中的记录进行排序，其主要操作是要通过一系列的比较使不在正确位置上的记录通过交换操作使之到达正确的位置上，一次交换操作可以交换两条记录的位置，因此提高排序效率的很重要的一个方面就是尽量减少记录移动的次数。 2 问题的提出 在实际问题中经常遇到这样一种特殊情况的排序，即对关键字个数有限的记录进行排序。例如，试图对某次竞赛的奖牌榜进行排序时就只有3个关键字，即：金牌、银牌和铜牌(或一等奖、二等奖和三等奖)，所有的金牌获得者在最前面，随后是银牌获得者，最后是铜牌获得者。要对奖牌榜排成符合要求的顺序而又要求用最少的交换次数来实现，对类似这样的问题我们可以用下面的题目来描述： 对于一个给定的只含有3个关键字的记录序列，将其按非递减顺序排列，要求交换次数最少。现假设关键字只有1、2、3(当然也可以是其它数据，比如9、20、57等)一个顺序存储的线性表，设计一个算法将该顺序表按非递减排序，要求交换次数最少。 3 算法分析 在众多排序算法中，选择法排序相对于其它排序方法来说，平均交换次数是最少的，尤其是在关键字杂乱无章的情况下使用选择法排序可以有效地减少交换次数。选择法的基本思想是：首先从序列中选择关键字最小的记录同第一条记录交换，再从余下的记录中选择关键字最小的与第二条记录交换，这样往复下去，直到全部记录排序完成。如对于如下的初始序列： 也就是原序列的第0条记录和第3条记录进行了交换操作，使原第3条记录到达了应该到达的正确位置，而原第0条记录到达了第3条记录的位置，但我们可以看出显然不是它应该到达的最终位置，所以至少还要需要一次交换操作才有可能使该记录最终到位。最终使上述序列排成非递减序列需要进行4次交换操作。其排序过程如下： 初始序列： 3 2 3 1 2 2 1 3 1 1 第一次交换后：1 2 3 3 2 2 1 3 1 1 第二次交换后：1 1 3 3 2 2 2 3 1 1 第三次交换后：1 1 1 3 2 2 2 3 3 1 第四次交换后：1 1 1 1 2 2 2 3 3 3 通过上述的分析，对关键字数量有限的记录排序，用选择法进行显然交换次数不是最少的。针对题目要求，如果我们在交换时尽可能地做到使两条记录同时到位，则交换次数肯定会少于选择法。 因为要排成非递减序列，所以关键字小的记录应该在序列的前半部分，而关键字大的记录应该在序列的后半部分。为此，我们可以按如下方法进行排序：假设a[low…high]是一维数组，我们让变量mid=(low+high)/2；指针i、j作为控制搜索的变量，指针i用来在记录的前半部分搜索，指针j用来在记录的后半部分搜索；指针frontmax用来记录数组前半部分中关键字值最大的记录位置，每次搜索其初始值都为low，指向第一个记录位置；指针backmin用来记录数组后半部分中关键字值最小的记录的位置，每次搜索时其初始值都为high，指向最后一个记录的位置；变量exchangenum记录交换的次数，其初始值为0。 排序的具体过程为：我们首先从序列的开始(第low条记录)在序列的前半部分搜索关键字值最大的记录，用变量frontmax来记录找到的关键字值最大的记录的位置；从序列的最后开始(第high条记录)在序列的后半部分中搜索关键字值最小的记录，用变量backmin记录序列后半部分中关键字值最小的记录位置。搜索完一遍后用frontmax指示的记录的关键字值a[frontmax]和backmin指示的记录的关键字值a[backmin]进行比较，若a[frontmax] > a[backmin]，说明这两个位置上的记录都不在正确的位置上，则这两个位置的记录要做一次交换，同时交换次数exchangenum增加1。由于序列关键字的数量是有限的，一次交换有可能使两条记录同时到位，这样就可以有效地减少记录交换的次数；若在搜索完后没有发生交换，说明前半部分中所有记录的关键字值都不大于后半部分中所有记录的关键字值，则结束本次搜索过程。然后将序列分为两个部分a[low…mid]和a[mid+1…high]，在这两个部分中分别执行上述过程，也就是对两部分分别进行递归调用，而交换次数也相应的为exchangenum=exchange num+前半部分交换的次数+后半部分交换的次数。 4 算法实现 经过上面的分析，我们给出实现上述过程的算法如下： 输入：n个元素的数组a[0..n-1] 输出：按非降序排列的数组a[0..n-1]，排序需要的元素交换次数exchangenum exchangenum=0； //初始交换次数为0 if 数组中的元素个数大于两个 then { mid=(low+high)/2； //mid为中间元素的位置 while (记录还没有搜索完成) { 在数组的前半部分搜索关键字值最大的记录位置， 用frontmax来记录该位置，其初始值为low； 在数组的后半部分中搜索关键字值最小的记录的位置， 用backmin来记录该位置，其初始值为high； if a[frontmax]>a[backmin] then { a[fonrtmax] a[backmin]； exchangenum = exchangenum+1； } if 没有交换 then { //分别在数组的前半部分和后半部分中进行递归处理； exchangenum+=前半部分的处理所需的交换次数+后半部分的处理所需的交换次数； } } else { //数组中的元素个数等于2 if(a[low]>a[high]) then { a[low] a[high]； exchangenum++； } } return exchangenum； //将交换次数返回

如对上面的序列操作过程用该方法操作示意图如下：

经过示意图上①、②、③步的交换之后，序列变成了下面的情况： 1 1 1 1 2 2 2 3 3 3 在本例中，我们发现只经过了3次交换序列就已经变成了非递减排序，而交换次数比使用选择法排序少1次。如果待排序的数据比较多，或者数据的原始位置不是像上面所举例子一样，则很可能经过第一遍的操作之后整个序列还没有完全达到要求，那么就将整个序列分成前后两部分，然后在两部分中分别实施上述过程，即递归进行处理。 下面给出用c语言实现上述算法的函数exchangesort： 调用方式：exchangesort(a[]，0，n-1) int exchangesort(int a[]，int low，int high) { int i，j，p，temp，mid； int frontmax，backmin， exchangenum=0； if(high-low>1) { mid=(low+high)/2； for(p=low；p<=mid；p++) { frontmax=low； backmin=high； for(i=low+1，j=high-1；i<=j；i++，j- -) { if(a[frontmax]<a[i]) frontmax=i； if(a[backmin]>a[j]) backmin=j； } if(a[frontmax]>a[backmin]) { temp=a[frontmax]； a[frontmax]=a[backmin]； a[backmin]=temp； exchangenum++； } else { exchangenum+=exchangesort(a，low，mid)+exchangesort(a，mid+1，high)； } } } else if(a[low]>a[high]) { temp=a[low]； a[low]=a[high]； a[high]=temp； exchangenum++； } return exchangenum； } 5 与使用选择法排序的比较 下面给出使用本算法和使用选择法进行处理的几组对照数据，从中可以看出在任何情况下使用本算法排序在交换次数上都少于使用选择法排序所需的交换次数。 第一组：最好情况，数据本身就有序 初始数据：1 1 1 1 2 2 2 3 3 3 使用选择法的交换次数：0 使用本算法的交换次数：0 第二组：最差情况，所有数据都不在正确位置上 初始数据：3 3 2 1 1 3 1 2 2 2 使用选择法的交换次数：7 使用本算法的交换次数：6 第三组：随机情况 初始数据：3 2 1 2 2 3 1 2 3 1 使用选择法的交换次数：5 使用本算法的交换次数：3 第四组：随机情况 初始数据：2 1 3 3 2 2 1 1 2 1 使用选择法的交换次数：5 使用本算法的交换次数：4 第五组：随机情况 初始数据：2 2 3 3 1 2 3 1 1 2 使用选择法的交换次数：7 使用本算法的交换次数：5 第六组：随机情况 初始数据：1 3 1 2 3 3 2 1 1 2 使用选择法的交换次数：6 使用本算法的交换次数：4 参考文献 [1] 谭浩强．c语言程序设计．北京：清华大学出版社，2000 [2] 严蔚敏，吴伟民．数据结构(c语言版)[m]．北京：清华大学出版社，1997 [3] m.h.alsuwaiyel著，吴伟，方世昌等译．算法设计技巧与分析．北京：电子工业出版社，2004.8