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

哈希表

ＩＳＳＮ１００９－３０４４Ｅ－ｍａｉｈｘｓｊｌ＠ｃｃｃｅ．ｎｅｔ．ＣｒｌＣｏｍｐｕｆｅｒＫｎｏｗｌｅｄｇｅａｎｄＴｅｃｈｎｏｌｏｇｙ电奠知识与技术ｈｔｔｐ：／／ｗｗｗ．ｄｎｚｓ．ｎｅｔ．ｃｎＶ０１．６．Ｎｏ．４，Ｆｅｂｒｕａｒｙ２０１０．ＰＰ．８５９—８６０Ｔｅｌ：＋８６．．５５１．—５６９０９６３５６９０９６４一种基于哈希链表的多关键字排序算法

董万归

（大理学院数学与计算机学院，云南大理６７１００３）

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

关键词：排序；哈希链表；关键字；算法设计

中图分类号：ＴＰ３０１文献标识码：Ａ文章编号：１００９—３０４４（２０１０）０４－０８５９－０２

ＡＳｏｒｔＡｌｇｏｒｉｔｈｍｏｆＭａｎｙＫｅｙｗｏｒｄｓＢａｓｅｄｏｎＨａｓｈＴａｂｌｅ

ＤＯＮＧＷａｎ—ｇｕｉ

（ＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＣｏｌｌｅｇｅ，ＤａｌｉＣｏＨｅｇｅ，Ｄａｌｉ６７１００３，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａＳｏｒｔＡｌｇｏｒｉｔｈｍｏｆｍａｎｙｋｅｙｗｏｒｄ．ｓｂａｓｅｄｏｎｈａｓｈｔａｂｌｅ，Ｔｈｅａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｄａｔａｅｌｅｍｅｎｔｓｏｆｔｈｅｋｅｙ—ｗｏｒｄｃｏｎｖｅｒｓｉｏｎ，Ｈａｓｈｔａｂｌｅｕｓｉｎｇｔｈｅａｄｄｒｅｓｓｍａｐｐｉｎｇｄａｔａｅｌｅｍｅｎｔｓｉｎａｎｏｒｄｅｒｌｙｓｅｑｕｅｎｃｅｏｆｌｏｃａｔｉｏｎｓ，ＴｈｅｒｅｂｙｒｅｄｕｃｉｎｇｔｈｅｋｅｙｗｏｒｄｃｏｍｐａｒｉｓｏｎａｎｄｓｏｒｔｉｎｇａｌｇｏｒｉｔｈｍＳＯｔｈａｔｔｈｅｍｏｂｉｌｅｏｐｔｉｍｉｚｅｄ．Ａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｈａｓｈｔａｂｌｅｔｏｉｍｐｒｏｖｅｆｒｏｍ，ｆｎｓｐｅｃｉｆｉｃｍａｎｙｋｅｙ—ｗｏｒｄｓｉｎａｃｅｒｔａｉｎｓｏｒｔｏｆａｐｐｌｉｃａｔｉｏｎ．

Ｋｅｙｗｏｒｄｓ：ｓｏｒｔ；ｈａｓｈｔａｂｌｅ；ｍｕｌｔｉｐｌｅｋｅｙｗｏｒｄｓ；ａｌｇｏｒｉｔｈｍｄｅｓｉｇｎ

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

ｌ算法描述

算法是基于多关键字转换及哈希链表来实现的，其基本思想是：根据多关键字的特点将其转换为单关键字，并将原始序列当成哈希链表闭：然后，对原始哈希链表进行一遍扫描根据转换过程中的哈希位置确定数据元素在哈希链表中的位置。假设待排数据元素有Ｎ个，数据元素的关键字比较有Ｍ个其排序优先级为Ｋ。＞Ｋ２＞…＞ＫＭ，Ｋ。…Ｋ。的范围为Ｌｃ＂ｌＪｍ。对于数据的存储可以定义如下结构来实现：

ｔｙｐｅｄｅｆｓｔｍ（＇ｔ

｛

Ｅｌｅｍｔｙｐｅｋｌ，ｋ２，…，ｋｍ；／＊ｍ个关键字定义４／

ｉｎｔｔｉｒｏｌ；／＊ｍ个关键字对应的权值定义｝／

ｉｎｔｌ【ｍ１；／＊ｍ个关键字的范围定义４，

…／半其它信息定义ｔ／

Ｌｏｎｇｎｏｄｅｐｏｓｉｔｉｏｎ；／木存放转换后的哈希位置＋／

ＮｏｄｅＴｙｐｅ＋ｐｒｉｏｒ，＊ｎｅｘｔ；

ｌＮｏｄｅＴｙｐｅ；

ＮｏｄｅＴｙｐｅＨｅａｄ，ｄａｔａ；

具体算法描述如下：

第一步：将原始数据序列存放到以Ｈｅａｄ为链表头的哈希链表中ｊ在放人的过程中对任意一个元素ｉ利用公式ｋ＝ｄａｔａ．ｄ１］４ｄａｔａ．１１２１＂ｄａｔａ．１１３］＊…＊ｄａｔａ．１【ｍ】＋ｄａｔａ．ｒ［２１＊ｄａｔａ．１１３１＂ｄａｔａ。１１４］＊…￥ｄａｔａ．１【ｍ】 …… 此处隐藏：2426字，全部文档内容请下载后查看。喜欢就下载吧 ……