超快速排序
超快速排序算法
周建钦
(安徽工业大学 计算机学院, 安徽马鞍山, 243002)
摘要: 快速排序算法结构简单,平均性能较佳; 基数排序性能较稳定。结合快速排序和基数排序，本文提出超快速排序算
法，通过理论分析和实验表明，新算法的性能优于快速排序算法和基数排序算法。
关键词: 排序；算法；快速排序；基数排序；超快速排序
中图法分类号: TP251; 文献标识码: A
排序(Sorting), 就是将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。 由于排序是计算机科
学中一项复杂而重要的技术,无论在系统软件还是在应用软件中使用频率都很高,因此许多专家、学者对排序问题进行了
深入的探讨,给出了许多时间复杂度仅为 O(N)的高效排序方法[1—5]。基数排序是典型的时间复杂度仅为 O(N)的算法之
一，但其算法结构较复杂，对于一些特殊数据要占用大量额外内存，故使用频率并不高。快速排序算法采用分治原则，
算法结构简单,平均性能较佳为 O(NlogN)，因而被广泛使用。但快速排序算法，在数据部分相等或有序时，时间复杂度
最坏为 O(N 2
)。侧重速度稳定排序算法的时候，往往使用归并排序或堆排序。
结合快速排序的分治算法结构和基数排序的原则，本文提出超快速排序算法。新算法保留了快速排序算法结构的简
洁性，同时速度稳定且优于快速排序算法和基数排序算法。
1．算法描述与分析
我们首先讨论无符号整数的排序.
关于十进制整数的基数排序，假设所有数据的最高位数为 m, 则先根据最高位（m 位） 的数字将数据分成 10 个小组；
对于每个小组的数据，根据次高位（m-1 位）的数字将数据分成 10 个小组；……，依此类推，最后根据个位（1 位）的
数字将数据分成 10 个小组,依此收集各个小组的数据，便将数据排序。其算法结构较复杂，对于一些特殊数据要占用大
量额外内存。
二进制整数的基数排序是一个非常特殊的情形，因为只有两个数字 0 和 1，故每次将数据分成 2 个小组。假设所有
数据属于[0，2
1 + m
-1], m 为一整数，则先根据最高位（m 位）的数字将数据分成 2 个小组，分别属于[0，2
m
-1]和[2
m
，
2
1 + m
-1]；根据次高位（m-1 位）的数字将[0，2
m
-1]的数据分成 2 个小组，分别属于[0，2
1 - m
-1]和[2
1 - m
，2
m
-1]，将[2
m
，
2
1 + m
-1]的数据分成 2 个小组，分别属于[2
m
，2
m
+2
1 - m
-1]和[2
m
+2
1 - m
，2
1 + m
-1]；……，这完全类似于快速排序的分治
算法结构，因而可以类似于快速排序实现该算法。
下面的算法 1 是递归形式的超快速排序算法,。
算法 1：超快速排序
设待排序数据存储于数组 a[]，下标范围为从 low 到 high，所有数据小于 2
1 + m
, 令 k=2
m
。
bq_sort(int *a , int low, int high, int k)
{
int i,j;
int x; // x 为临时变量
i=low;
j=high;
while(i<j)
{
while(a[j]&k && i<j )j--;
while((a[i]&k)==0 && i<j )i++;
if(i<j)
{
x=a[j];
a[j]=a[i];
a[i]=x;
}
else
{
if(a[j]&k)i--;
else j++;
break;
}
}
if(k>1)
{
if(low<i)bq_sort(a,low,i,k/2);
if(j<high)bq_sort(a,j,high,k/2);
}
}
若 n 个待排序数据存储于数组 a[],下标从 0 到 n-1。假设所有数据小于 2
1 + m
, m为一整数，则调用该算法的形式为：
bq_sort(0,n-1, 2
m
)。若 a[i]& 2
m
为 1,即 a[i]作为二进制,其 m位为 1；反之，若 a[i]& 2
m
为 0,即 a[i]作为二进制,其 m位为
0。第二次以形式 bq_sort(low,i, 2
1 - m
)调用该算法，即根据 m-1 位来分组 a[low]到 a[i]的数据。
来自自然界和社会的数据都有一定的变化范围,例如年龄和经济数据等。另外, 计算机处理的数据也有字长的限制,
因而可以假设所有数据小于 2
1 + m
, m为一整数。如果关键字数据类型为字长 16 比特的整数类型，则 m 最大为 15。在数
据分布不均匀的情况，可能出现某个小组数据个数小于 2，或者根据最低位分组后仍有多个相等数据，两种情况下超快
速排序算法都会终止相应的递归，因而其最坏时间复杂度为 O(N(m+1))=O(N)。
一般的基数排序算法结构较复杂，分配和收集数据时需要占用大量额外内存。超快速排序算法最多需要存放 m-1 次
递归调用的变量，不需要其他额外内存。
2．实验结果和结论
表 1 是对快速排序，归并排序，基数排序（8 进制）和超快速排序用 C 语言在 Celeron2.0G 上做的一个比较,表中同
一列分别为用快速排序，归并排序，基数排序（8 进制）和超快速排序处理同样数量的随机数据(由 RAND 函数产生)所
用时间,单位为毫秒 ms.
表 1
数据个数 20,000 200,000 2,000,000 20,000,000
快速排序 4 42 466 13608
归并排序 4 52 573 6191
基数排序(8 进制) 4 32 400 110000
超快速排序 4 32 297 2978
实验表明, 算法 1 实现的超快速排序算法不但继承了基数排序速度稳定的优点，而且其速度明显快于快速排序、归
并排序和基数排序(8 进制)。由此看来，超快速排序算法是名副其实的。
对于有符号整数,在调用 bq_sort 之前, 首先根据符号位将所有数据分成两部分, 只是符号位为1 的数据放在前面, 符
号位为 0 的数据放在后面，然后再分别调用 bq_sort 即可。在计算机中，副整数是以补码形式存放的，因而 bq_sort 最终
将所有数据按由小到大顺序排序。
对于浮点型数据，容易转换为整数，然后可以使用超快速排序。对于非数字型数据，如英文单词的排序，可以先将
英文单词截成长度为 5 的等长字符串（长度小于 5 时用空格补齐） ，令空格，A，B，…，Z 分别对应 0，1，2，…，26，
则等长字符串即对应 27 进制整数。使用超快速排序算法排序后，对应的英文单词已经基本有序，只有长度大于 5 的英
文单词可能未排序。再使用简单插入排序算法（该算法当数据基本有序时速度相当快）直接排序即可。
参考文献
[1] 卢开澄, 组合数学算法与分析(下册)[M].北京：清华大学出版社，1983
[2] 严蔚敏,吴伟民, 数据结构[M].北京：清华大学出版社，1997
[3] 周建钦,赵志远,排序和查找理论及算法[M].北京：科学出版社，1993
[4] 唐向阳,分段快速排序法[J].软件学报,1993,4(2):53-57
[5] 王向阳,任意分布数据的基数分配链接排序算法[J].计算机学报,2000,23(7):774-778
[6] D.Cantone,G.Cincotti, QuickHeapsort: an efficient mix of classical sorting algorithms, Theoretical Computer Science
285(2002)25-42
Super quick sort algorithm
Jianqin Zhou
Dept. of Computer Science
Anhui University of Technology
Ma’anshan,Anhui 243002,PRC
Abstract: Sorting algorithms have been widely studied in both theory and algorithm design. We present super quick sort, a
new practical “in-place” sorting algorithm obtained by merging some characteristics of radix sort and quick sort. Both
theoretical analysis and experimental tests confirm the merits of super quick sort. The time complexity and space complexity of
the new algorithm is much better than that of both radix sort and quick sort.
Keywords: sort; algorithm; quick sort; radix sort; super quick sort
---------------------------------------------------------------------------------------------------------
*** 《超快速排序算法》一文的附件一 ***
RESUME
------------------------------------------------------------------------------------------------
Name: Jianqin Zhou
Sex: Male
Date of birth: Jan 6,1963
------------------------------------------------------------------------------------------------
Education:
1986-1989 Statistics Department, Fudan University, Shanghai,
P.R.China, Master of Science in Statistics.
1979-1983 Mathematics Department, East China Normal University,
Shanghai,P.R.China,Bachelor of Science in Mathematics
------------------------------------------------------------------------------------------------
Career Summary:
Professor, Department of Computer Science,
Anhui University of Technology.
Published more than thirty five papers, one paper
proved a conjecture posed by famous mathematician
Paul Erdos et al. Research interests include theoretical
computer science, combinatorics and algorithm.
------------------------------------------------------------------------------------------------
*** 《超快速排序算法》一文的附件二 ***
《超快速排序算法》一文的说明
⑴《超快速排序算法》一文无泄密之处，未发表和未一稿多投。
⑵ 分类号 (中图)TP251;
⑶ 周建钦
安徽工业大学计算机学院 （安徽马鞍山,243002）
*** 《超快速排序算法》一文的附件三 ***
《超快速排序算法》中作比较的其他三个算法程序
快速排序
q_sort(int *a , long low, long high)
{
long i,j;
int x;
i=low; j=high;
x=a[i];
while(i<j)
{
while(a[j]>=x && i<j)j--;
a[i]=a[j];
while(a[i]<=x && i<j)i++;
a[j]=a[i];
}
a[i]=x;
if(i–low>1)q_sort(a,low,i-1);
if(high –j>1)q_sort(a,j+1,high);
}
下面的算法将一维数组 t2[]中前后向邻的两个有序序列归并为数组 t1[]中一个有序序列。
归并两组已排序数据
merge(int *t2,int *t1,int low, int m, int high)
{
int i,j,k;
i=k=low; j=m+1;
while(i<=m && j<=high)
{
if(t2[i]<=t2[j])t1[k++]=t2[i++];
else t1[k++]=t2[j++];
}
while(i<=m )t1[k++]=t2[i++];
while(j<=high )t1[k++]=t2[j++];
}
下面的算法是递归形式的二路归并排序算法。
归并排序
m_sort(int *a, int *t1,int *t2, int low, int high)
{
int m;
if(low==high && t1!=a)t1[low]=a[low];
if(low<high)
{
m=(low+high)/2;
m_sort(a,t2,t1,low,m);
m_sort(a,t2,t1,m+1,high);
merge(t2,t1,low,m,high);
}
}
下面的算法是递归形式的基数排序(8 进制)算法, 例如二字节整数,调用形式为 b8q_sort(0,n-1,12)。
基数排序(8 进制)
b8q_sort(long low,long high,int m)
{
long i,j,k;
int x;
int start[8],cur[8];
for(i=0;i<8;i++)
start[i]=cur[i]=-1;
for(i=low;i<=high; i++)
{
x=(a[i]>>m)%8;
if(start[x]==-1)
{
start[x]=i;
cur[x]=i;
}
else
{
b[cur[x]]=i;
cur[x]=i;
}
}
for(i=0;i<8;i++)
b[cur[i]]=-1;
j=low;
for(i=0;i<8;i++)
{
k=start[i];
start[i]=j;
while(k>-1){c[j]=a[k];k=b[k];j++;};
}
for(i=low;i<=high; i++) a[i]=c[i];
if(m)
{
for(i=0;i<7;i++)
if(start[i+1]-start[i]>1)b8q_sort(start[i],start[i+1]-1,m-3);
if(high-start[7]>0)b8q_sort(start[7],high,m-3);
}
}