位排序 -- 基于计数排序和基数排序产生的特例

liangbch

while (i bitx(X [ j],k) //元素想x[ i ]的第k比特大于X[j]的第k比特 X [i ] <--> X[ j ] //交换x[ i ]与x[j] i++; j--; }

这个逻辑有问题，等我有空儿时订正它。

liangbch

以下是我写的位排序代码，包含排序函数和测试程序

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <memory.h>
5. typedef unsigned long DWORD;
6. typedef int BOOL;
8. #define TRUE 1
9. #define FALSE 0
11. #define MAX_LEN 65536
13. DWORD data[MAX_LEN];
14. DWORD databak[MAX_LEN];
16. void printArray(DWORD *p, int len);
18. //bit 排序核心算法，这是一个递归函数
19. void bitSort(DWORD *p, int begin, int end, DWORD mask )
20. {
21. int i=begin;
22. int j=end;
24. if ( j==i+1 && p[j]>=p[ i ])
25. return;
26. if ( mask<=0)
27. return ;
28. while (i<j)
29. {
30. DWORD t;
31. while ( (p[ i ] & mask) ==0 && i<=end)
32. i++;
33. while ( (p[j] & mask) >0 && j>=begin)
34. j--;
36. if (i<j)
37. {
38. t=p[ i ];
39. p[ i ]=p[j];
40. p[j]=t;
41. }
42. }
44. mask/=2; i--; j++;
45. if (i>begin)
46. {
47. bitSort(p,begin,i,mask);
48. }
50. if (j<end)
51. {
52. bitSort(p,j,end,mask);
53. }
54. }
56. //使用 bit sort 对数组p 进行排序
57. void mySort1(DWORD *p, int len)
58. {
59. DWORD max=p[0];
60. DWORD mask=2147483648;
61. int i;
63. if (len<2)
64. return;
66. for (i=1;i<len;i++)
67. {
68. if (p [ i ] > max)
69. max=p[ i ];
70. }
72. while ( mask > max)
73. mask/=2;
74. bitSort(p,0,len-1,mask);
75. }
77. //打印数组
78. void printArray(DWORD *p, int len)
79. {
80. int i;
81. for (i=0;i<len;i++)
82. {
83. if (i>0)
84. printf(",");
85. printf("%u",p[ i ]);
86. }
87. printf("\n");
88. }
90. //检查数组是否是增序排列
91. BOOL checkArray(DWORD *p,int len)
92. {
93. int i;
94. BOOL ret=TRUE;
95. for (i=0;i<len-1;i++)
96. {
97. if (p[i+1]< p[ i ] )
98. {
99. ret=FALSE; break;
100. }
101. }
103. return ret;
104. }
106. //bit排序测试程序，产生1 到 MAX_LEN，对长度为1到 MAX_LEN的数组进行排序
107. void testBitSort()
108. {
109. int i,j;
110. for (i=1;i<=MAX_LEN;i++)
111. {
112. for (j=0;j<i;j++)
113. {
114. data[j]= (rand() & 255);
115. }
117. memcpy(databak,data,i*sizeof(DWORD));
118. mySort1(data,i);
120. if ( !checkArray(data,i) )
121. {
122. printf("error\n");
124. printf("Before sort\n\t");
125. printArray(databak,i);
127. printf("After sort\n\t");
128. printArray(data,i);
129. break;
130. }
131. }
132. }
134. int main(int argc, char* argv[])
135. {
136. testBitSort();
137. return 0;
138. }

复制代码

liangbch

10# liangbch 当关键字的范围很窄是，可比较 ( p[ i ] - min)的第k比特，速度可大大加快。比如有1百万个数，关键字的范围为 1000000 到 1000200。 则其复杂度为 8*1百万,因为 p[ i ] - min 的范围为0 到 200， 第1遍检测 bit7,第2遍检测 bit6,第8遍检测 bit0。

silitex

10# liangbch 当关键字的范围很窄是，可比较 ( p[ i ] - min)的第k比特，速度可大大加快。比如有1百万个数，关键字的范围为 1000000 到 1000200。 则其复杂度为 8*1百万,因为 p[ i ] - min 的范围为0 到 200， ... liangbch 发表于 2009-11-3 18:52

感谢您的回答，程序中也考虑了关键字很窄的时候的范围，比如取值范围为：1000000 到 1000200，是则Hash成：0~200，那么就等于用8位(2^8=256)排序即可！(传入了UNIQUE_HASH_CALLBACK pUniqueHashFunc这个参数就是为了针对每一个不同的数据传入不同的Hash函数，以便做特殊处理) 您的算法我再花时间看看!

silitex

关于位排序，前人已有研究。请看 http://bbs.emath.ac.cn/viewthrea ... &fromuid=25#pid9829。 快速扫了你代码中的注释，感觉你的这个实现不太好，需要分配额外的空间。 《无符号整数按位快速排序算法》基本思想是 ... liangbch 发表于 2009-11-3 15:02

呵呵，在写完这个位排序算法的时候，我看的就是您提供的前人的位排序算法，后来经过VC的单步跟踪，发现前人的位排序算法在边值判断上（会有重复判断的可能）要处理得没有那么好。 也很感谢您的批评和指正！ 哎，做了一件前人做过的事情，还好这个事情不难做，没浪费多少时间！

silitex

看完了您的代码： 其中： # if (i # while ( (p[ i ] & mask) ==0 && i<=end) # i++; # while ( (p[j] & mask) >0 && j>=begin) # j--;

liangbch

哈哈，说点儿题外话，个人感觉那篇论文的代码很复杂，而且有错，不能编译。感觉作者的编程功底不是很好。现在有好多“学者”，就是为了写论文写论文。 你的代码写的很工整！不错！

liangbch

7# silitex 学术氛围使然，有些人就是喜欢弄虚作假。

liangbch

看完了您的代码： 其中： # if (i=begin) # j--; silitex 发表于 2009-11-4 09:09

很不幸，你的修改时错的，你增加i++,j--这行代码，然后运行一下我的测试程序就明白了。

liangbch

看了一下周建钦写的那篇文章，本质上和我的代码是一致的。