摘要：快速排序算法结构简单，平均性能较佳；基数排序算法性能较稳定。结合快速排序和基数排序，本文提出超快速排序算法，通过理论分析和实验表明，新算法的性能优于快速排序算法和基数排序算法。
算法
排序(Sorting), 就是将数据元素(或记录)的一个任意序列，重新排列成一个按关键字有序的序列。由于排序是计算机科学中一项复杂而重要的技术，无论在系统软件还是在应用软件中使用频率都很高，因此许多专家、学者对排序问题进行了深入的探讨，给出了许多时间复杂度仅为 O(N)的高效排序方法[1—5]。基数排序是典型的时间复杂度仅为 O(N)的算法之一，但其算法结构较复杂，对于一些特殊数据要占用大量额外内存，故使用频率并不高。快速排序算法采用分治原则，算法结构简单，平均性能较佳为 O(NlogN)，因而被广泛使用。但快速排序算法，在数据部分相等或有序时，时间复杂度最坏为 O(N2)。侧重速度稳定的排序算法的时候，往往使用归并排序或堆排序。
结合快速排序的分治算法结构和基数排序的原则，本文提出超快速排序算法。新算法保留了快速排序算法结构的简洁性，同时速度稳定且优于快速排序算法和基数排序算法。
1．算法描述与分析
我们首先讨论无符号整数的排序.
关于十进制整数的基数排序，假设所有数据的最高位数为 m, 则先根据最高位（m 位）的数字将数据分成 10 个小组；对于每个小组的数据，根据次高位（m-1 位）的数字将数据分成 10 个小组；……；依此类推，最后根据个位（1 位）的数字将数据分成 10 个小组，依此收集各个小组的数据，便将数据排序。其算法结构较复杂，对于一些特殊数据要占用大量额外内存。
二进制整数的基数排序是一个非常特殊的情形，因为只有两个数字 0 和 1，故每次将数据分成 2 个小组。假设所有数据属于[0，21+m-1], m 为一整数，则先根据最高位（m 位）的数字将数据分成 2 个小组，分别属于[0，2m-1]和[2m，21 + m-1]；根据次高位（m-1 位）的数字将[0，2m-1]的数据分成 2 个小组，分别属于[0，21 - m-1]和[21 - m，2m-1]，将[2m，21 + m-1]的数据分成 2 个小组，分别属于[2m，2m+21 - m-1]和[2m+21 - m，21 + m-1]；……；这完全类似于快速排序的分治算法结构，因而可以类似于快速排序实现该算法。
下面的算法 1 是递归形式的超快速排序算法,。
超快速排序
设待排序数据存储于数组 a[]，下标范围为从 low 到 high，所有数据小于 21 + m, 令 k=2m。
若 n 个待排序数据存储于数组 a[],下标从 0 到 n-1。假设所有数据小于 21 + m, m为一整数，则调用该算法的形式为：
bq_sort(0,n-1, 2m)。
若 a[i]\u0026 2m为 1,即 a[i]作为二进制，其 m位为 1；反之，若 a[i]\u0026 2m为 0,即 a[i]作为二进制，其 m位为0。第二次以形式
bq_sort(low,i, 21 - m)
调用该算法，即根据 m-1 位来分组 a[low]到 a[i]的数据。
来自自然界和社会的数据都有一定的变化范围，例如年龄和经济数据等。另外, 计算机处理的数据也有字长的限制，因而可以假设所有数据小于 21 + m, m为一整数。如果关键字数据类型为字长 16 比特的整数类型，则 m 最大为 15。在数据分布不均匀的情况，可能出现某个小组数据个数小于 2，或者根据最低位分组后仍有多个相等数据，两种情况下超快速排序算法都会终止相应的递归，因而其最坏时间复杂度为 O(N(m+1))=O(N)。
一般的基数排序算法结构较复杂，分配和收集数据时需要占用大量额外内存。超快速排序算法最多需要存放 m-1 次递归调用的变量，不需要其他额外内存。
实验结果结论
表 1 是对快速排序，归并排序，基数排序（8 进制）和超快速排序用 C 语言在 Celeron2.0G 上做的一个比较，表中同一列分别为用快速排序，归并排序，基数排序（8 进制）和超快速排序处理同样数量的随机数据(由 RAND 函数产生)所用时间，单位为毫秒 ms.
实验表明, 算法 1 实现的超快速排序算法不但继承了基数排序速度稳定的优点，而且其速度明显快于快速排序、归并排序和基数排序(8 进制)。由此看来，超快速排序算法是名副其实的。
对于有符号整数，在调用 bq_sort 之前, 首先根据符号位将所有数据分成两部分, 只是符号位为1 的数据放在前面, 符号位为 0 的数据放在后面，然后再分别调用 bq_sort 即可。在计算机中，副整数是以补码形式存放的，因而 bq_sort 最终将所有数据按由小到大顺序排序。
对于浮点型数据，容易转换为整数，然后可以使用超快速排序。
对于非数字型数据，如英文单词的排序，可以先将英文单词截成长度为 5 的等长字符串（长度小于 5 时用空格补齐） ，令空格，A，B，…，Z 分别对应 0，1，2，…，26，则等长字符串即对应 27 进制整数。使用超快速排序算法排序后，对应的英文单词已经基本有序，只有长度大于 5 的英文单词可能未排序。再使用简单插入排序算法（该算法当数据基本有序时速度相当快）直接排序即可。
比较其他程序
快速排序
q_sort(int *a , long low, long high)
{
long i,j;
int x;
i=low; j=high;
x=a[i];
while(i\u003cj)
while(a[j]\u003e=x \u0026\u0026 i\u003cj) j--;
a[i]=a[j];
while(a[i]\u003c=x \u0026\u0026 i\u003cj) i++;
a[j]=a[i];
}
a[i]=x;
if(i–low\u003e1) q_sort(a,low,i-1);
if(high –j\u003e1) 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\u003c=m \u0026\u0026 j\u003c=high)
{
if(t2[i]\u003c=t2[j]) t1[k++]=t2[i++];
else t1[k++]=t2[j++];
}
while(i\u003c=m ) t1[k++]=t2[i++];
while(j\u003c=high ) t1[k++]=t2[j++];
}
递归形式排序
m_sort(int *a, int *t1,int *t2, int low, int high)
{
int m;
if(low==high \u0026\u0026 t1!=a) t1[low]=a[low];
if(low\u003chigh)
{
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(long low,long high,int m)
{
long i,j,k;
int x;
int start,cur;
for(i=0;i\u003c8;i++)
start[i]=cur[i]=-1;
for(i=low;i\u003c=high; i++)
{
x=(a[i]\u003e\u003em)%8;
if(start[x]==-1)
{
start[x]=i;
cur[x]=i;
}
else
{
b[cur[x]]=i;
cur[x]=i;
}
}
for(i=0;i\u003c8;i++)
b[cur[i]]=-1;
j=low;
for(i=0;i\u003c8;i++)
{
k=start[i];
start[i]=j;
while(k\u003e-1)
{
c[j]=a[k];k=b[k];j++;
}
for(i=low;i\u003c=high; i++) a[i]=c[i];
if(m)
{
for(i=0;i\u003c7;i++)
if(start[i+1]-start[i]\u003e1) b8q_sort(start[i],start[i+1]-1,M3);
if(high-start\u003e0 ) b8q_sort(start,high,m-3);
}
}