Home > Old Blog Posts > QD的排序算法

QD的排序算法


用决策树可以证明,基于比较的排序算法运行时间的下界是O(nlogn),但一些不基于比较的排序,可以突破这个下界,如基数排序、桶排序等,这些排序可以达到O(n)的运行时间,但往往需要格外的存储空间,实在恼人。
今日在网上神游之时,忽然发现一种很强大的整数排序算法,这种算法结合了快速排序的框架,和基数排序的思想,号称“超快速排序算法”,其实,其更专业一些的名字应该是基于二进制的基数排序。
算法的思想大概是这样的,首先找到待排序的数中最高的位数,从高位往低位,对于每一位,若为0则被划分到数组的左边,若为1则划分到数组的右边,然后递归计算下一位。
代码大致如下:

void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
void super_quicksort(int left, int right, int k)
{
int i,j,x;
i=left,j=right;
while(i<j)
{
while(a[j]&k &&i<j) j–;
while(!(a[i]&k) &&i<j) i++;
if(i<j)
swap(&a[i],&a[j]);
else
{
if(a[j]&k) i–;
else j++;
break;
}
}
if(k>1)
{
if(left<i) super_quicksort(left,i,k>>1);
if(j<right) super_quicksort(j,right,k>>1);
}
}

是不是与快速排序很像呢?若不仔细看,你或许会认为,唯一的不同就是多了一个参数k吧。
BTW,在编程中,若调用排序的数组并不是很多,最好不要把数组写入函数参数中,而将数组设为全局变量,这样可以节省一定的运行时间。

我将它与朴素的快速排序的运行时间进行了比较(运行环境为Windows XP, Intel双核2.00GHZ, 2G内存):

数据:20000000个0~100000之间的数
quicksort 30.35s
super-quicksort 4.16s
很明显的差距吧

数据:20000000个0~10000000之间的数
quicksort 30.20s
super-quicksort 4.60s
后者的时间稍有加长,因为super的运行时间会随着k的增大而变长。

数据:20000000个10000000(相同数据)
quicksort too long……
super-quicksort 1.88s

由上可见,这种算法具有很QD的运行时间,而对于信息学竞赛来说,有史以来,NOIP所要用到排序的基本上都是整数的排序,因此,这种算法有很大的用武之地。

附录 我用的quicksort的代码:

void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
int partition(int left, int right)
{
int i=(left+right)>>1,j;
swap(&A[i],&A[right]);
i=left-1;
for(j=left;j<right;j++)
{
if(A[j]<A[right])
{
i++;
swap(&A[i],&A[j]);
}
}
i++;
swap(&A[i],&A[right]);
return i;
}
void quicksort(int left, int right)
{
int i;
if(left<right)
{
i=partition(left,right);
quicksort(left,i-1);
quicksort(i+1,right);
}
}

参考文献:《超快速排序算法》 周建钦

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: