超快速排序算法
需积分: 9 33 浏览量
2016-04-20
13:34:12
上传
评论
收藏 89KB PDF 举报
计算机工程与应用
２００６．２９
１
引言
排序（
Ｓｏｒｔｉｎｇ
） ， 就是 将 数据 元 素（ 或记 录 ） 的一个 任 意序
列， 重新排列成一个按关键字有序的序列。由于排序是计算机
科学中一项复杂而重要的技术
， 无论在系统软件还是在应用软
件中使用频率都很高， 因此许多专家、学者对排序问题进行了
深入的探讨
， 给出了许多时间复杂度仅为
Ｏ
（
Ｎ
） 的高效排序方
法
［１～５］
。基数排序是典型的时间复杂度仅为
Ｏ
（
Ｎ
） 的算法之一，
但其算法结构较复杂， 对于一些特殊数据要占用大量额外内
存， 故使用频率并不高。快速排序算法采用分治原则， 算法结构
简单
， 平均性能较佳为
Ｏ
（
ＮｌｏｇＮ
） ， 因而被广泛使用。但快速排
序算法， 在数据部分相等或有序时， 时间复杂度最坏为
Ｏ
（
Ｎ
２
） 。
侧重速度稳定排序算法的时候
， 往往使用归并排序或堆排序。
结合快速排序的分治算法结构和基数排序的原则， 本文提
出超快速排序算法。新算法保留了快速排序算法结构的简洁
性
， 同时速度稳定且优于快速排序算法和基数排序算法。
２
算法描述与分析
我们首先讨论无符号整数的排序。
关于十进制整数的基数排序
， 假设所有数据的最高位数为
ｍ
， 则先根据最高位（
ｍ
位） 的数字将数据分成
１０
个小组； 对于
每个小组的数据
， 根据次高位（
ｍ－ １
位） 的数字将数据分成
１０
个小组； 等等， 依此类推， 最后根据个位（
１
位） 的数字将数据分
成
１０
个小组， 依此收集各个小组的数据， 便将数据排序。其算
法结构较复杂， 对于一些特殊数据要占用大量额外内存。
二进制整数的基数排序是一个非常特殊的情形， 因为只有
两个数字
０
和
１
， 故每次将数据分成
２
个小组。假设所有数据
属于
［０
，
２
ｍ＋１
－ １］
，
ｍ
为一整数， 则先根据最高位（
ｍ
位） 的数字将
数据分成
２
个小组， 分别属于
［０
，
２
ｍ
－ １］
和
［２
ｍ
，
２
ｍ＋１
－ １］
； 根据次高
位（
ｍ－ １
位） 的数字将
［０
，
２
ｍ
－ １］
的数据分成
２
个小组， 分别属于
［０
，
２
ｍ－ １
－ １］
和
［２
ｍ－ １
，
２
ｍ
－ １］
， 将
［２
ｍ
，
２
ｍ＋１
－ １］
的数据分成
２
个小组， 分
别属于
［２
ｍ
，
２
ｍ
＋２
ｍ－１
－ １］
和
［２
ｍ
＋２
ｍ－ １
，
２
ｍ＋１
－ １］
； 等等， 这完全类似于快
速排 序 的分 治 算法 结 构， 因而 可 以类 似 于快 速 排序 实 现 该
算法。
下面的算法
１
是递归形式的超快速排序算法， 。
算法
１
超快速排序
设待排序数据存储于数组
ａ［］
， 下标范围为从
ｌｏｗ
到
ｈｉｇｈ
，
所有数据小于
２
ｍ＋１
， 令
ｋ＝２
ｍ
。
ｂｑ＿ｓｏｒｔ
（
ｉｎｔ ＊ａ
，
ｉｎｔ ｌｏｗ
，
ｉｎｔ ｈｉｇｈ
，
ｉｎｔ ｋ
）
｛
ｉｎｔ ｉ
，
ｊ
；
ｉｎｔ ｘ
；
／ ／ ｘ
为临时变量
ｉ＝ｌｏｗ
；
ｊ＝ｈｉｇｈ
；
ｗｈｉｌｅ
（
ｉ＜ｊ
）
｛
ｗｈｉｌｅ
（
ａ［ｊ］＆ｋ ＆＆ ｉ＜ｊ
）
ｊ－ －
；
ｗｈｉｌｅ
（ （
ａ［ｉ］＆ｋ
）
＝＝０ ＆＆ ｉ＜ｊ
）
ｉ＋＋
；
ｉｆ
（
ｉ＜ｊ
）
｛
ｘ＝ａ［ｊ］
；
ａ［ｊ］＝ａ［ｉ］
；
ａ［ｉ］＝ｘ
；
｝
ｅｌｓｅ
｛
ｉｆ
（
ａ［ｊ］＆ｋ
）
ｉ－ －
；
ｅｌｓｅ ｊ＋＋
；
超快速排序算法
周建钦
（ 安徽工业大学计算机学院， 安徽马鞍山
２４３００２
）
摘 要 快速排序算法结构简单， 平均性能较佳； 基数排序性能较稳定。结合快速排序和基数排序， 提出超快速排序算
法， 通过理论分析和实验表明， 新算法的性能优于快速排序算法和基数排序算法。
关键词 排序 算法 快速排序 基数排序 超快速排序
文章编号
１００２－ ８３３１
（
２００６
）
２９－ ００４１－ ０２
文献标识码
Ａ
中图分类号
ＴＰ２５１
Ｓｕｐｅｒ Ｑｕｉｃｋ Ｓｏｒｔ Ａｌｇｏｒｉｔｈｍ
ＺＨＯＵ Ｊｉａｎ－ ｑｉｎ
（
Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ
，
Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ
，
Ｍａ
’
ａｎｓｈａｎ
，
Ａｎｈｕｉ ２４３００２
）
Ａｂｓｔｒａｃｔ
：
Ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｈａｖｅ ｂｅｅｎ ｗｉｄｅｌｙ ｓｔｕｄｉｅｄ ｉｎ ｂｏｔｈ ｔｈｅｏｒｙ ａｎｄ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎ．Ａ ｎｅｗ ｐｒａｃｔｉｃａｌ
“
ｉｎ－ ｐｌａｃｅ
”
ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍ
，
ｃａｌｌｅｄ ｓｕｐｅｒ ｑｕｉｃｋ ｓｏｒｔ
，
ｉｓ ｏｂｔａｉｎｅｄ ｂｙ ｍｅｒｇｉｎｇ ｓｏｍｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｒａｄｉｘ ｓｏｒｔ ａｎｄ ｑｕｉｃｋ ｓｏｒｔ．Ｂｏｔｈ
ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｉｓ ａｎｄ ｅｘｐｅｒｉｍｅｎｔａｌ ｔｅｓｔｓ ｃｏｎｆｉｒｍ ｔｈｅ ｍｅｒｉｔｓ ｏｆ ｓｕｐｅｒ ｑｕｉｃｋ ｓｏｒｔ．Ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｓｐａｃｅ ｃｏｍ－
ｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｕｃｈ ｂｅｔｔｅｒ ｔｈａｎ ｔｈａｔ ｏｆ ｂｏｔｈ ｒａｄｉｘ ｓｏｒｔ ａｎｄ ｑｕｉｃｋ ｓｏｒｔ．
Ｋｅｙｗｏｒｄｓ
：
ｓｏｒｔ
，
ａｌｇｏｒｉｔｈｍ
，
ｑｕｉｃｋ ｓｏｒｔ
，
ｒａｄｉｘ ｓｏｒｔ
，
ｓｕｐｅｒ ｑｕｉｃｋ ｓｏｒｔ
基金项目： 国家自然科学基金资助项目（ 编号：
６０４７３１４２
）
作者简介： 周建钦（
１９６３－
） ， 男， 教授， 研究方向为： 理论计算机科学， 算法和组合数学。
４１
资源评论
