silitex
发表于 2009-11-4 14:05:26
很不幸，你的修改时错的，你增加i++,j--这行代码，然后运行一下我的测试程序就明白了。
liangbch 发表于 2009-11-4 12:18 http://bbs.emath.ac.cn/images/common/back.gif
厄，呵呵，在您的代码上如果仅仅增加i++,和j--这两行，是还不行的（当然，这也是我没有表达清楚意思，抱歉）。所以如果要解决不多判断一次，又让这个代码运行不出错，需要再另外处理一下，我的代码就进行了这样的一个处理。当然，话说回来，是我太追求细节了，为了尽量减少判断次数及移动次数，进行了单步跟踪及修正（自嘲）。
非常高兴和您的沟通！
silitex
发表于 2009-11-4 14:07:29
看了一下周建钦写的那篇文章，本质上和我的代码是一致的。
liangbch 发表于 2009-11-4 12:31 http://bbs.emath.ac.cn/images/common/back.gif
是的，不过周在描述时间复杂度时疏漏了，应该为O（nlogm）（进行了n长度的logm次扫描），当然空间复杂度就是O（logm）（因为递归深度为logm）了
gxqcn
发表于 2009-11-5 07:44:01
两位对此均有研究，探讨就可以更深入了。:)
〇〇
发表于 2009-11-5 09:04:03
继续学习
liangbch
发表于 2009-11-5 10:48:04
21# silitex
对核心部分进行了优化，消除了潜在的错误。
//bit 排序核心算法，这是一个递归函数
void bitSort(DWORD *p, int begin, int end, DWORD mask )
{
int i=begin;
int j=end;
DWORD t;
if ( mask<=0)
return ;
if (i>=j)
return;
while (i<j)
{
while ( (p[ i ] & mask) ==0 && i<=j)
i++;
while ( (p & mask) >0 && i<=j)
j--;
if (i<j)
{
t=p[ i ]; p[ i ]=p; p=t;
i++;
}
}
if (j<begin || i>end) //没有左半部分,或者右半部分
{
bitSort(p,begin,end,mask/2);
}
else
{
bitSort(p,begin,i-1,mask/2);
bitSort(p,i,end,mask/2);
}
}
liangbch
发表于 2009-11-5 11:10:42
周建钦写的代码，变量名称和数据类型稍有改动
//周建钦写的排序函数void zjq_sort(DWORD *a,int low,int high,DWORD mask)
{
int i,j;
DWORD x; // x为临时变量
i=low;
j=high;
while(i<j)
{
while ( (a & mask) && i<j )j--;
while ( (a & mask)==0 && i<j) i++;
if(i<j)
{
x=a;
a=a;
a=x;
}
else
{
if( a & mask) i--;
else j++;
break;
}
}
if(mask>1)
{
if(low<i)zjq_sort(a,low,i,mask/2);
if(j<high) zjq_sort(a,j,high,mask/2);
}
}
silitex
发表于 2009-11-6 09:11:35
:)，学习了！liangbch写代码还真是认真啊！