while (i<j)
{
ifbitx( X[ i ],k) > bitx(X [ j],k) //元素想x[ i ]的第k比特大于X的第k比特
X <--> X[ j ]//交换x[ i ]与x
i++;
j--;
}
这个逻辑有问题，等我有空儿时订正它。
本帖最后由 liangbch 于 2009-11-3 18:43 编辑
以下是我写的位排序代码，包含排序函数和测试程序#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef unsigned long DWORD;
typedef int BOOL;
#define TRUE 1
#define FALSE 0
#define MAX_LEN 65536
DWORD data;
DWORD databak;
void printArray(DWORD *p, int len);
//bit 排序核心算法，这是一个递归函数
void bitSort(DWORD *p, int begin, int end, DWORD mask )
{
int i=begin;
int j=end;
if ( j==i+1 && p>=p[ i ])
return;
if ( mask<=0)
return ;
while (i<j)
{
DWORD t;
while ( (p[ i ] & mask) ==0 && i<=end)
i++;
while ( (p & mask) >0 && j>=begin)
j--;
if (i<j)
{
t=p[ i ];
p[ i ]=p;
p=t;
}
}
mask/=2; i--; j++;
if (i>begin)
{
bitSort(p,begin,i,mask);
}
if (j<end)
{
bitSort(p,j,end,mask);
}
}
//使用 bit sort 对数组p 进行排序
void mySort1(DWORD *p, int len)
{
DWORD max=p;
DWORD mask=2147483648;
int i;
if (len<2)
return;
for (i=1;i<len;i++)
{
if (p [ i ] > max)
max=p[ i ];
}
while ( mask > max)
mask/=2;
bitSort(p,0,len-1,mask);
}
//打印数组
void printArray(DWORD *p, int len)
{
int i;
for (i=0;i<len;i++)
{
if (i>0)
printf(",");
printf("%u",p[ i ]);
}
printf("\n");
}
//检查数组是否是增序排列
BOOL checkArray(DWORD *p,int len)
{
int i;
BOOL ret=TRUE;
for (i=0;i<len-1;i++)
{
if (p< p[ i ] )
{
ret=FALSE; break;
}
}
return ret;
}
//bit排序测试程序，产生1 到 MAX_LEN，对长度为1到 MAX_LEN的数组进行排序
void testBitSort()
{
int i,j;
for (i=1;i<=MAX_LEN;i++)
{
for (j=0;j<i;j++)
{
data= (rand() & 255);
}
memcpy(databak,data,i*sizeof(DWORD));
mySort1(data,i);
if ( !checkArray(data,i) )
{
printf("error\n");
printf("Before sort\n\t");
printArray(databak,i);
printf("After sort\n\t");
printArray(data,i);
break;
}
}
}
int main(int argc, char* argv[])
{
testBitSort();
return 0;
}
10# liangbch
当关键字的范围很窄是，可比较 ( p[ i ] - min)的第k比特，速度可大大加快。比如有1百万个数，关键字的范围为 1000000 到 1000200。 则其复杂度为 8*1百万,因为 p[ i ] - min 的范围为0 到 200， 第1遍检测 bit7,第2遍检测 bit6,第8遍检测 bit0。
本帖最后由 silitex 于 2009-11-4 09:15 编辑
10# liangbch
当关键字的范围很窄是，可比较 ( p[ i ] - min)的第k比特，速度可大大加快。比如有1百万个数，关键字的范围为 1000000 到 1000200。 则其复杂度为 8*1百万,因为 p[ i ] - min 的范围为0 到 200， ...
liangbch 发表于 2009-11-3 18:52 http://bbs.emath.ac.cn/images/common/back.gif
感谢您的回答，程序中也考虑了关键字很窄的时候的范围，比如取值范围为：1000000 到 1000200，是则Hash成：0~200，那么就等于用8位(2^8=256)排序即可！(传入了UNIQUE_HASH_CALLBACK pUniqueHashFunc这个参数就是为了针对每一个不同的数据传入不同的Hash函数，以便做特殊处理)
您的算法我再花时间看看!
本帖最后由 silitex 于 2009-11-4 14:11 编辑
关于位排序，前人已有研究。请看 http://bbs.emath.ac.cn/viewthrea ... &fromuid=25#pid9829。
快速扫了你代码中的注释，感觉你的这个实现不太好，需要分配额外的空间。
《无符号整数按位快速排序算法》基本思想是 ...
liangbch 发表于 2009-11-3 15:02 http://bbs.emath.ac.cn/images/common/back.gif
呵呵，在写完这个位排序算法的时候，我看的就是您提供的前人的位排序算法，后来经过VC的单步跟踪，发现前人的位排序算法在边值判断上（会有重复判断的可能）要处理得没有那么好。
也很感谢您的批评和指正！
哎，做了一件前人做过的事情，还好这个事情不难做，没浪费多少时间！
看完了您的代码：
其中：
# if (i<j)
# {
# t=p[ i ];
# p[ i ]=p;
# p=t;
# }
这里因为没有进行一次i++和j--，所以下次循环的时候又需要在当前位置再判断一次，所以造成了判断次数的增加！（我最开始也是这样做的，呵呵，后来单步跟踪的时候发现这里有多余的判断，所以在他们交换值完毕的时候立即进行了一次i++和j--，以便下次循环不用再判断了）
您的这段写得比我简洁，学习了！:b:
# while ( (p[ i ] & mask) ==0 && i<=end)
# i++;
# while ( (p & mask) >0 && j>=begin)
# j--;
哈哈，说点儿题外话，个人感觉那篇论文的代码很复杂，而且有错，不能编译。感觉作者的编程功底不是很好。现在有好多“学者”，就是为了写论文写论文。
你的代码写的很工整！不错！
7# silitex
学术氛围使然，有些人就是喜欢弄虚作假。
看完了您的代码：
其中：
# if (i=begin)
# j--;
silitex 发表于 2009-11-4 09:09 http://bbs.emath.ac.cn/images/common/back.gif
很不幸，你的修改时错的，你增加i++,j--这行代码，然后运行一下我的测试程序就明白了。
看了一下周建钦写的那篇文章，本质上和我的代码是一致的。