2024年4月30日发(作者：)

！　Ｑ：　

Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｎｏｖａｔｉｏｎ　Ｈｅｒａｌｄ　

Ｔ技术　

基数排序算法的链表实现　

敖友云　

（安庆师范学院计算机与信息学院　安徽安庆　２４６０　１　１）　

摘要：比较关键字和移动记录是实现算法排序的两个基本操作。在经典排序算法中，基数排序是一种不通过比较关键字实现排序的方　

法。通过示倒说明了基数排序算法的基本思想，用Ｃ程序设计语言以链表为存储结构实现了基数排序算法，并分析了基数排序算法的计算　

复杂性。　

关键词：算法　排序　基数排序　链表　

中图分类号：ＴＰ３Ｉ　２　文献标识码：Ａ　文章编号：１６７４－－０９　８Ｘ（２０１１）０８（ｂ）一００２３—０２　

３）按百位数分配和收集数据结点，分配　

排序是计算机处理数据序列最常用的　

１基数排序算法的基本思想　

一

种操作。排序操作将一组无序的数据序　

列按某种次序重新排列，从而得到一组有　

序的数据序列，以方便用户的查找，提高检　

索数据的效率。下面给出排序的概念：　

定义１：设有一个由　个记录Ｒ＝｛Ｒ　ｌｆ　

＝１，２…．，　｝构成的有限序列，这　个记录对　

应的关键字序列为ｋ＝｛ｋｉＩ　＝１，２…．，　｝。　

排序就是确定１，２…．，ｎ的一种排列Ｐ。，Ｐ：，　

…，

ｐ　，使得ｋ　ｋ口，　…　ｋＰ　（或ｋ　ｐ１　

ｋ　…　ｋ　），并通过调整Ｒ中记录的位　

置，得到一个新的按关键字非递减（或非递　

增）的有序序列Ｒ’＝｛Ｒ　Ｒ　，…．，　｝的　

过程。　

排序在处理数据序列的计算机程序中　

占用的时间较长，设计高效的排序算法是　

提高这些程序执行效率的关键。通常，排序　

算法通过两个基本操作实现对数据序列排　

序：一个是通过比较关键字来确定数据在　

数据序列中的位置次序；另一个是将数据　

从一个位置移动到另一个位置，从而调整　

数据在数据序列中的位置次序。这两个基　

本操作很大程度上决定排序算法的计算效　

率。依据算法的平均时间复杂性，将常用的　

排序算法分为三类：简单排序算法，时间复　

杂性为Ｏ（ｎ　），例如，直接插入排序、起泡排　

序、简单选择排序；先进排序算法，时间复　

杂性为ｏ（ｎｌｂｇ　），例如，希尔排序、快速排　

序、堆排序、　并排序；基数排序，时间复杂　

性为Ｏ（ｄ・ｎ）　基数排序在关键字个数　为　

一

常数时，时间复杂性Ｄ（＂）是线性的。基　

数排序是一种不通过比较关键字实现排序　

的方法，它借助多关键字排序的思想对单　

逻辑关键字进行排序。　

算法和数据结构是计算机程序设计和　

软件开发的基础。依据“程序＝算法＋数据　

结构”的观点，程序、算法和数据结构三者　

联系密切。链表是一种比较简单、实用的　

数据结构。排序算法采用链表结构实现对　

数据序列排序，进行插入或删除操作，只　

需修改指针，可以避免移动大量记录，从　

而节省时间。因此，本文首先结合实例介　

绍了基数排序算法的基本思想，然后采用　

链表结构通过程序的方式实现了基数排　

序算法，并分析了基数排序算法的计算复　

杂性。　

设有一个由ＲＡＤＩｘ个单链表组成的链　到链表集Ｌ中的数据结点的分布位置：Ｌ［０】　

表集Ｌ【　０，１，．．．，ＲＡＤＩＸ一１和一个由　

＝

｛８，６３，８３｝，Ｌ［１】＝｛ｌ０９，１８４｝，Ｌ［２１＝｛２６９，　

ＲＥＣＮＵＭ个数据元素组成的单链表Ｈｅａｄ＝　

２７８｝，Ｌ［５】＝｛５０５，５８９｝，Ｌ［９］＝｛９３０｝；收集到　

｛ａｌ，ａ２，．．．，ａＲＥＣ　｝，每个数据元素由　

单链表Ｈｅａｄ中的数据结点的相应位置：　

ＫＥＹＮＵＭ个关键字组成，每个关键字的表　

Ｈｅａｄ＝｛９３０，５８９，５０５，２７８，２６９，１８４，１０９，８３，　

达式为，七ＫＥＹＮＬＪＭ七ＫＥＹＮＵＭ　一　七１，０　＜　

６３，８｝。　

ＲＡＤⅨ则基数排序算法的步骤如下：　

最后，将单链表Ｈｅａｄ中的数据按逆序　

１）ｆ＝１　ｌ　

传回给数组，得到有序数组ａ为｛８，６３，８３，　

２）依据单链表Ｈｅａｄ中每个数据元素的　

ｌ０９，ｌ　８４，２６９，２７８，５０５，５８９，９３０｝。　

第ｆ位关键字上的数字ｋｉ，把数据结点取下　

分配￣ＵＲＡＤＩＸ个链表集Ｌ中，分配的原则是　

２基数排序算法的链表实现　

关键字ｋｉ＝Ｊ的数据结点，都分配到链表　

下面给出了基数排序算法的Ｃ语言程　

Ｌ［ｊ］中；　

序代码。程序已在ＶＣ＋＋环境下测试通过。　

３）依次序将链表集Ｌ［ｉ］，　＝０，１，．．．，　

程序中包含下述主要模块：创建单链表　

ＲＡＤⅨ一１中的全部数据结点取下收集，并　

ＣｒｅａｔｅＩＪｉｎｋＬｉｓｔ（ＡｒｒＴｙｐｅ　ａ）、基数排序算法　

链接这些结点构成一个新的单链表Ｈｅａｄ；　

的核心模块ＲａｄｉｘＳｏｒｔ（ＡｒｒＴｙｐｅ　ａ）。　

４）ｆ自增１，若ｆ　ＫＥＹＮＵＭ，返回２），否　

＃ｉｎｃｌｕｄｅ”ｓｔｄｉｏ．ｈ”　

则结束。　

＃ｉｎｃｌｕｄｅ”ｍａｔｈ．ｈ”　

下面通过示例进一步说明基数排序算　

＃ｉｎｃｌｕｄｅ”ｍａｌｌｏｃ．ｈ”　

法的基本思想。　

＃ｄｅｆｉｎｅ　ＲＡＤＩＸ　１０　／／基数ｌ０为　

例如，基数排序前数组ａ为　

十进制数　

｛２７８，１Ｏ９，６３，９３０，５８９，ｌ８４，５０５，２６９，　

＃ｄｅｆｉｎｅ　ＫＥＹＮＵＭ　３／／记录中关键　

８，８３｝　

字的个数　

数组ａ中记录的个数ＲＥＣＮＵＭ＝ｌ０，基　

＃ｄｅｆｉｎｅ　ＲＥＣＮＵＭ　１０／／记录的个数　

数ＲＡＤＩｘ：１０为十进制数，数据的最高位为　

ｔｙｐｅｄｅｆ　ｉｎｔ　ＡｒｒＴｙｐｅ［ＲＥＣＮＵＭ】；　

百位，因此关键字的个数ＫＥＹＮＵＭ＝３。首　

ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ＬＮｏｄｅ｛／／定义单链表　

先，根据数组ａ提供的数据元素建立一个单　

结构　

链表Ｈｅａｄ＝｛８３，８，２６９，５０５，１８４，５８９，９３０，　

ｉｎｔ　ｄａｔａ；　

６３，１０９，２７８｝。考虑到数据元素有３个关键　

ｓｔｒｕｃｔ　ＬＮｏｄｅ＊ｎｅｘｔ；　

字，因此需要依次按个位、十位和百位在单　

｝ＬＮｏｄｅ，＊ＬｉｎｋＬｉｓｔ　ｌ　

链表ＨｅａｄＳＨ链表集Ｌ之间进行分配和收集　

ｔｙｐｅｄｅｆ　ＬＮｏｄｅ　ＳＬＬｉｓｔ［ＲＡＤＩＸ】；　

数据结点，具体过程如下：　

ＬｉｎｋＬｉｓｔ　ＣｒｅａｔｅＬｉｎｋＬｉｓｔ（ＡｒｒＴｙｐｅ　ａ）　

１）按个位数分配和收集数据结点，分配　

／／创建单链表　

到链表集Ｌ中的数据结点的分布位置：Ｌ［０】　

｛ｉｎｔ　ｉ；ＬｉｎｋＬｉｓｔ　Ｈｅａｄ，Ｐ；　

＝

｛９３０｝，Ｌ［３］＝｛６３，８３｝，Ｌ【４】＝｛１８４｝，Ｌ［５］＝　

Ｈｅａｄ＝（ＬＮｏｄｅ＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；　

｛５０５｝，Ｌ［８】＝｛２７８，８｝，Ｌ【９】＝｛１０９，５８９，２６９｝ｌ　

Ｈｅａｄ－＞ｎｅｘｔ＝ＮＵＬＬ　ｔ　

收集到单链表Ｈｅａｄ中的数据结点的相应位　

ｆｏｒ（ｉ＝０ｌｉ＜ＲＥＣＮＵＭＩｉ＋＋）｛　

置：Ｈｅａｄ＝｛２６９，５８９，１０９，８，２７８，５０５，１８４，　ｐ＝（ＬＮｏｄｅ＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；　

８３，６３，９３０｝。　Ｐ一＞ｄａｔａ＝ａ［ｉ】ｌ　

２）按十位数分配和收集数据结点，分配　

ｐ－＞ｎｅｘｔ＝Ｈｅａｄ－＞ｎｅｘｔｌＨｅａｄ一＞　

到链表集Ｌ中的数据结点的分布位置：Ｌ［Ｏ］　

ｎｅｘｔ　Ｐ；　

＝

｛５０５，８，１０９｝，Ｌ【３］：｛９３０｝，Ｌ【６］＝｛６３，２６９｝，　｝　．　

Ｌ［７］＝｛２７８｝，Ｌ【８】＝｛８３，ｌ８４，５８９｝；收集到单　

ｒｅｔｕｒｎ　Ｈｅａｄ；　

链表Ｈｅａｄ中的数据结点的相应位置：Ｈｅａｄ＝　

｝　

｛５８９，１　８４，８３，２７８，２６９，６３，９３０，ｌ０９，８，　

ｖｏｉｄ　ＲａｄｉｘＳｏｒｔ（ＡｒｒＴｙｐｅ　ａ）　

５０５｝。　｛ＳＬＬｉｓｔ　ＬｌＬｉｎＩ【Ｌｉｓｔ　Ｈｅａｄ，ｐ，ｑｌｉｎｔ　ｉ，ｊ，ｋ；　

科技创新导报Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｎｏｖａｔｉｏｎ　Ｈｅｒａｌｄ　２３　

！！　Ｑ：垫　

Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｎｏｖａｔｉｏｎ　Ｈｅｒａｌｄ　

Ｔ技术　

ｆｏｒ（ｉ＝０　ｌ　ｉ＜ＲＡＤＩＸ；ｉ＋＋）／／初始化链表　

ｖｏｉｄ　ｍａｉｎ（）　

大而记录中关键字的个数较小的序列。　

集Ｌ　｛ｉｎｔ　ｉ；　

｛Ｌ［ｉ］．ｄａｔａ＝ｉ；Ｌ［ｉ】．ｎｅｘｔ＝ＮＵＬＬ；｝　

ＡｒｒＴｙｐｅ　ａ＝｛２７８，１０９，６３，９３０，５８９，　

４结语　

Ｈｅａｄ＝ＣｒｅａｔｅＬｉｎｋＬｉｓｔ（ａ）｝／／０］建单链表　

１８４，５０５，２６９，８，８３｝；　

与其它排序算法相比，基数排序算法　

Ｈｅａｄ　

ｐｒｉｎｔｆ（”＼ｎＴｈｅ　ｏｒｉｇｉｎａｌ　ａｒｒａｙ：”）；　

不通过比较关键字实现对序列排序，具有　

ｆｏｒ（ｉ＝０　Ｉ　ｉ＜ＫＥＹＮＵＭ；ｉ＋＋）｛　

ｆｏｒ（ｉ＝０；ｉ＜ＲＥＣＮＵＭ；ｉ＋＋）ｐｒｉｎｔｆ（”％ｄ　计算时间复杂度较低的优点。本文基数排　

／／分配Ｈｅａｄ中的数据结点到Ｌ中　

”

，

ａ［ｉ】）ｌ　

序算法采用链表存储结构实现，具有思路　

ｐ＝Ｈｅａｄ－＞ｎｅｘｔ；Ｈｅａｄ－＞ｎｅｘｔ＝ＮＵＬＬ｛　

ＲａｄｉｘＳｏｒｔ（ａ）；　

清晰、结构简单、易于扩充以及容易实现等　

ｗｈｉｌｅ（ｐ）｛　

ｐｒｉｎｔｆ（”＼ｎＴｈｅ　ａｒｒａｙ　ｈａｓ　ｂｅｅｎ　ｓｏｒｔｅｄ：　特点。将来的研究工作是在海量数据上对　

ｑ＝ｐ｛ｐ＝ｐ－＞ｎｅｘｔ　ｌ　

”）；　

本文算法进一步测试，并与其它排序算法　

ｋ＝（ｑ一＞ｄａｔａ／（ｉｎｔ）ｐｏｗ（ＲＡＤＩＸ，ｉ））　

ｆｏｒ（ｉ＝０；ｉ＜ＲＥＣＮＵＭ；ｉ＋＋）ｐｒｉｎｔｆ（”％ｄ　

进行定量比较。另外，对本文程序的核心模　

％ＲＡＤＩＸｔ　

”

，

ａ【ｉ】）；　

块的正确性证明也是进一步的研究工作。　

ｑ一＞ｎｅｘｔ＝Ｌ［ｋ］．ｎｅｘｔ；Ｌ［ｋ】．ｎｅｘｔ＝ｑ｝　

｝　

｝／／ｗｈｉｌｅ　

参考文献　

／／收集Ｌ中的数据结点到Ｈｅａｄ中　

３基数排序算法的计算复杂性分析　

［１］严蔚敏，吴伟民．数据结构（Ｃ语言版）　

ｆｏｒ（ｊ＝０；ｊ＜ＲＡＤＩＸ　ｌｊ＋＋）｛　

设数据序列中需要排序的记录个数为　

［Ｍ］．北京：清华大学出版社．１９９７．　

ｐ＝Ｌ［ｊ】．ｎｅｘｔ；ＬＤ】．ｎｅｘｔ＝ＮＵＬＬ；　

ｎ，记录中关键字的个数为　，记录中存放　

［２］徐寿芳．一种新的高效基数排序算法　

ｗｈｉｌｅ（ｐ）｛　

的是ｒ进制数。则基数排序过程中，初始化　

［Ｊ】．湖州职业技术学院学报．２００８，（１）：　

ｑ＝ｐ；ｐ＝ｐ－＞ｎｅｘｔ；　

链表集Ｌ的时间复杂性为Ｄ（ｒ），创建单链　

１７～ｌ９．　

ｑ－＞ｎｅｘｔ＝Ｈｅａｄ－＞ｎｅｘｔ；　

表Ｈｅａｄ的时间复杂性为Ｄ（　），ｄ次分配　

［３］何文明．一种改进后的基数排序算法　

Ｈｅａｄ－＞ｎｅｘｔ＝ｑ；　

与收集数据结点的时间复杂性为Ｏ（ｄ・ｎ），　

［Ｊ］．湘潭大学自然科学学报．２００４，２６　

｝／／ｗｈｉｌｅ　

将单链表Ｈｅａｄ中的数据结点传回数组ａ　

（４）：３４～３８．　

｝／／ｆｏｒ　

的时间复杂性为Ｄ（　）。因此，基数排序算　

［４］卢开澄．计算机算法导引一设计与分析　

｝／／ｆｏｒ　

法的时间复杂性为Ｏ（ｄ・　）。当ｄ为一个固　

（第２版）［Ｍ］．北京：清华大学出版社．　

／／释放单链表Ｈｅａｄ，并将排序结果返　定常数时，基数排序算法的时间复杂性　

２００６．　

回数组ａ　

Ｄ（　）是线性的。另外，基数排序过程中额　

［５】葛浩，杨传健．基于分布计数的基数排　

Ｐ＝Ｈ　ｅａｄ一＞ｎｅｘｔ；ｆｒｅｅ（Ｈ　ｅａｄ）ｌ　

外用到ｎ数据结点，每个数据结点包含一　

序方法的研究［Ｊ］．计算机技术与发展．　

ｉ：ＲＥＣＮＵＭ－１　ｔ　

个数据域和一个指针域，单链表Ｈｅａｄ用到　

２００８，１８（２）：１２２～１２５．　

ｗｈｉｌｅ（ｐ）｛ｑ＝ｐｌｐ＝ｐ一＞ｎｅｘｔ；ａ［ｉｌ＝ｑ－＞　

一

个头结点，链表集Ｌ用到ｒ个头结点。因　【６］王向阳．任意分布数据的基数分配链接　

ｄａｔａ；ｆｒｅｅ（ｑ）｛ｉ一一；｝　

此，基数排序算法的辅助空间复杂性为　

排序算法【Ｊ】．计算机学报．２０００，２３（７）：　

｝　０（　）。基数排序算法比较适合记录个数较　

７７４～７７８．　

（上接２２页）　

用户的控制；（５）具有ＧＳＭ短信、射频、红外　

两大热点话题，已经逐渐开始受到人们越　

多，比如蓝牙，ＷＩＦＩ，ＷＡＰ……这些控制方　三种控制方式，系统稳定性提供，同时方便　

来越多的关注，因此将来应该有个不错的　

式为物联网的控制提供了技术支持，方便　用户选择合适的方式进行控制。　

发展前景。　

了用户的选择，同时多种控制方式也能提　

高系统的稳定性与可靠性。　

３物联网控制与节能技术展望　

参考文献　

２．３节能控制　

目前物联网的通信基础依旧是互联　［１】范志辉，李云龙．基于ＧＳＭ的环境综合　

传统的电器元件在工作完成之后通常　

网，但是未来的物联网一定不仅仅是互联　

监控系统软件设计［Ｊ］．微型电脑应用，　

不会自动断电（比如计算机完成计算任务　

网，应该更多的整合其它通信方式，比如移　

２０１０，２６（５）　

后通常不会自动关闭）或者用户离开室内　

动网络等。其次，应建立统一的控制管理平　［２］吴红燕，潘海民，赵存华，王松德．红外　

时忘记关闭电器，等到了室外才想起来电　台。每一户家庭都有很多的电器需要控制，　

遥控调速调光节能开关的设计［Ｊ】．煤矿　

源还未切断，这种情况下传统的电器还会　因此电器控制这一方面未来也会呈现出巨　机械，２００９，３０（３）　

继续消耗电能。使用我们设计的家用节能　大的市场，为了提高管理的效率，建立统一　

［３］陈庆霆，武林．基于ＧＳＭ的分布式稻田　

开关系统配合电器一起使用，当用户忘记　的控制管理平台，可以由用户为各个电器　

水位远程监控系统［Ｊ】．仪器仪表学报，　

关闭电源到室外又想来的时候，可以发送　设定具体的运行参数，平台对各电器运行　

２００９，３０（６）　

指令ＭＳＥＴＯＦＦ给指定的号码，ＧＳＭ短信模　

的状况进行检测控制，还要考虑安全等因　［４］杨仁渊．基于ＧＳＭ的远程控制报警系统　

块收到指令后，便会将连接在上面的电器　素。第三，应融入更多的传感控制技术。我　

［Ｊ］．２ｌ世纪人才培养，２００８，１　５（４）．　

元件的电源断开达到节能的目的；或者在　

们设计的家用节能控制系统中只简单地应　

［５】宜彩平，王皓，邹国良．利用ＧＳＭ无线模　

启动模块的时候使用指令ＭＳＥＴＯＮ４０，这　

用了红外、短信、射频控制技术，其实还有　块发送短消息　．计算机应用，２００４，２４　

里的“４Ｏ”表示电器工作４Ｏ分钟后自动断电，　

很多其它的控制技术来实现控制，比如说　

（５）．　

从而达到节能的目的。　蓝牙，ＷＩＦＩ，ＷＡＰ等控制方式，但是不同的　

【６】颜志国，唐前进．物联网技术在智能交　

２．４创新点　．　

控制方式要考虑系统运行的稳定性、可靠　

通中的应用［Ｊ】．警察技术，２０１０：ｌ１．　

（１）设计的家用节能开关系统适用于不　

性和系统设计及运行的成本等因素。节能　［７］蒋林涛．互联网与物联网【Ｊ】．电信工程　

同类型家庭电器，适用性较强；（２）系统操作　

方面可以通过设定更恰当的判定规则来实　

技术与标准化，２０１０（２）．　

和控制简便，用户可以非常容易地学习、使　

现，比如当外界的条件满足什么样的条件　

用；（３）系统可以实现无接触控制电路的通　

时触发系统自动切断用电器的电源。　

断，安全，便捷，（４）系统具有延时功能，方便　

总体来说，物联网和节能技术目前的　

２４　科技创新导报Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｎｏｖａｔｉｏｎ　Ｈｅｒａｌｄ