一种基于哈希链表的多关键字排序算法

摘要:该文结合哈希表提出一种多关键字的排序算法,该算法根据数据元素的关键字转换,利用哈希表的地址映射实现数据元素在有序序列中的位置,从而通过减少关键字比较及移动使排序算法得到优化。算法基于哈希表改进而来,在特殊多关键字排序中具有一定的应用。

关键词:排序;哈希链表;关键字;算法设计

中图分类号:TP301 文献标识码:A文章编号:1009-3044(2010)04-0859-02

A Sort Algorithm of Many Keywords Based on Hash Table

DONG Wan-gui

(Mathematics and Computer College, Dali College, Dali 671003, China)

Abstract: This paper presents a Sort Algorithm of many keywords based on hash table, The algorithm based on data elements of the keyword conversion, Hash table using the address mapping data elements in an orderly sequence of locations, Thereby reducing the keyword comparison and sorting algorithm so that the mobile optimized. Algorithm based on the hash table to improve from, In specific many keywords in a certain sort of application.

Key words: sort; hash table; multiple keywords; algorithm design

排序,就是要将一个序列R1,R2,…,Rn,使之按关键字K1,K2,…,Kn递增(或递减)排列起来,使得结果序列Ril,Ri2,…,Rin中满足Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)[1]。排序是程序设计中一种基本常用的操作,在实际程序设计中应用非常广泛,因此排序算法的好坏直接影响到程序的执行操作,进而影响到数据库的执行效率。在其它很多问题中,排序都是作为其中的一个基本过程,排序算法的好坏直接影响到整个问题解决的效率。当前,排序算法种类繁多,但就其排序时所遵循的原则而言,大致可分为五大类:插人排序、交换排序、选择排序、归并排序和基数排序。算法性能的好坏则主要是从时间复杂度、空间复杂度和稳定性三个方面考虑[2]。这些传统的排序方法大部分都是基于关键字的比较和序列元素的交换操作来实现,然而,对于一些实际应用中需要处理的数据却要求对多关键字进行排序,所以征对多关键字特定数据经过转换后的特定排序算法可以大大提高数据处理的速度。本文所描述的排序算法就是根据数据元素的关键字转换,利用哈希链表的地址映射实现数据元素在有序序列中的位置,从而通过减少关键字比较及移动使排序算法得到优化。

1 算法描述

算法是基于多关键字转换及哈希链表来实现的,其基本思想是:根据多关键字的特点将其转换为单关键字,并将原始序列当成哈希链表[3]。然后,对原始哈希链表进行一遍扫描根据转换过程中的哈希位置确定数据元素在哈希链表中的位置。假设待排数据元素有N个,数据元素的关键字比较有M个其排序优先级为K1>K2>…>KM, K1…KM的范围为L1…Lm。对于数据的存储可以定义如下结构来实现:

typedef struct

{

Elemtype k1,k2,…,km; /*m个关键字定义*/

int r[m]; /*m个关键字对应的权值定义*/

int l[m]; /*m个关键字的范围定义*/

… /*其它信息定义*/

Long nodeposition; /*存放转换后的哈希位置*/

NodeType *prior,*next;

}NodeType;

NodeTypeHead,data;

具体算法描述如下:

第一步:将原始数据序列存放到以Head为链表头的哈希链表中;在放入的过程中对任意一个元素i利用公式k=data.r[1]* data.l[2]* data.l[3]*…*data.l[m]+ data.r[2]* data.l[3]* data.l[4]*…* data.l[m] +…+ data.rm就可以计算出第i个元素在哈希链表中的位置k,将k放入辅助链表哈希位置变量nodeposition中。

第二步:对哈希链表利用哈希位置nodeposition进行单关键字排序。由于利用了链表进行操作可以使数据元素的移动转化为链表指针的重新指向。

第三步:对哈希链表中的数据进行回收,完成排序。

2 算法应用实例

以对当前车牌号序列进行排序为例,每一个车牌号由五个数字或字符组成,决定每个车牌号大小由五个关键字组成,在比较任意两个车牌号的大小时,要按车牌号的第一位到最后一位比较直到比较出大小。如果经过转换则可以只对一个数据进行比较就可以完成两个车牌号的比较。

首先,我们完成准备信息,车牌号的任意一位可能有36种情况,大小顺序为0

typedef struct

{

char carid[5];

int r[4],l[4];

Long nodeposition;

NodeType *prior,*next;

} NodeType;

NodeTypeHead,data;

接下来,将原始车牌号序列存放到以Head为链表头的哈希链表中,并利用公式计算出各车牌号的哈希位置。如某个车牌号为“56DF7”放入当前结点date中可用如下代码完成:

strcpy(data.carid,“56DF7”);

for(i=0 to 5)

{

data.r[i]=(int)(data.carid[i]) - 48;

data.L[i]=36;

}

Data.nodeposition= data.r[0]* data.l[1]* data.l[2]* data.l[3]* data.l[4]+ data.r[1]* data.L[2] * data.l[3]* data.l[4]+…+ data->r[4];

完成以后data中各对应分量的值分别为:carrid=”56DF76”, r[0]=5, r[1]=6 , r[2]=20 , r[3]=22 , r[4]=7,l[0]到l[4]都为36,nodeposition=5*36*36*36*36 + 6*36*36*36 + 20*36*36 + 22*36 + 7=8704735。

最后,就可以对链表中的数据利用插入排序算法以各接点中的哈希位置为关键字进行排序。当然,也可以在对键表进行赋值的同时进行排序,完成排序以后,回收链表中有用的数据就是可以得到最终的排序结果。

3 算法性能分析

算法性能的量度取决于算法执行时间和执行存储需求,分别称为时间复杂度和空间复杂度[4]。时间复杂度的根本意义上就是程序执行语句的频度,求出算法中语句执行的频度就可以求出算法的时间复杂度。而空间复杂度则是对一个算法在运行过程中临时占用存储空间大小的量度[5]。所以时间复杂度分析,就是语句执行频度的分析[6]。根据上面算法的描述,其语句执行频度多项式为:

f(n) ≈ n+1+n*m+n=(3+m)n+2

当n很大时算法的主要执行语句频度为3n,所以其渐近时间复杂度为O(n)。对于算法的空间复杂度,在排序过程中算法主要开辟了三个长度为n的整型(长整形)辅佐空间,所以其空间复杂度为O(n)。

4 结论

本文所描述的排序算法在整个排序过程中只用到单关键字的比较,数据元素的交换最多也只需进行n次,对于最坏情况下其时间复杂度也只为O(n)。在多关键字排序算法中很多时候使用的是基数排序[7],虽然其时间复杂度也只为O(n),但基数排序过程中要进行数据元素的分配和回收对一些数据类型来说是难于实现的且对于关键字范围大的情况下空间复杂度高。而本文所描述的算法特别适合于大记录大数据量的多关键字排序。

参考文献:

[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].4版.北京:清华大学出版社,2007.

[2] Weiss M A.数据结构与算法分析[M].北京:机械工业出版社,2004.

[3] 王川,王岁花.地址哈希排序算法的设计与实现[J].平原大学学报,2004,21(5):61-63.

[4] 廖荣贵,许正宪,王龙发,等.数据结构与算法[M].北京:清华大学出版社,2004.

[5] 王晓东.计算机算法与分析[M].北京:电子工业出版社,2001.

[6] 黄敏敏,康晓蓉.排序算法浅探[J].西南科技大学:高教研究,2006(1):16-18.

[7] 胡云.几种快速排序算法实现的比较[J].安庆师范学院学报:自然科学版,2008,14(3):100-103.