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

liangbch

while (i<j)
  {
      if  bitx( X[ i ],k) > 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>
   
4. 
   
5. typedef unsigned long DWORD;
   
6. typedef int BOOL;
   
7. 
   
8. #define TRUE        1
   
9. #define FALSE        0
   
10. 
    
11. #define MAX_LEN        65536
    
12. 
    
13. DWORD data[MAX_LEN];
    
14. DWORD databak[MAX_LEN];
    
15. 
    
16. void printArray(DWORD *p, int len);
    
17. 
    
18. //bit 排序核心算法，这是一个递归函数
    
19. void bitSort(DWORD *p, int begin, int end, DWORD mask )
    
20. {
    
21.         int i=begin;
    
22.         int j=end;
    
23.                
    
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--;
    
35.                
    
36.                 if (i<j)
    
37.                 {
    
38.                         t=p[ i ];
    
39.                         p[ i ]=p[j];
    
40.                         p[j]=t;
    
41.                 }
    
42.         }
    
43.        
    
44.         mask/=2;        i--;        j++;
    
45.         if (i>begin)
    
46.         {
    
47.                 bitSort(p,begin,i,mask);
    
48.         }
    
49.        
    
50.         if (j<end)
    
51.         {
    
52.                 bitSort(p,j,end,mask);
    
53.         }
    
54. }
    
55. 
    
56. //使用 bit sort 对数组p 进行排序
    
57. void mySort1(DWORD *p, int len)
    
58. {
    
59.         DWORD max=p[0];
    
60.         DWORD mask=2147483648;
    
61.         int i;
    
62.        
    
63.         if (len<2)
    
64.                 return;
    
65. 
    
66.         for (i=1;i<len;i++)
    
67.         {
    
68.                 if (p [ i ] > max)
    
69.                         max=p[ i ];
    
70.         }
    
71. 
    
72.         while ( mask > max)
    
73.                 mask/=2;
    
74.         bitSort(p,0,len-1,mask);
    
75. }
    
76. 
    
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. }
    
89. 
    
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.         }
     
102. 
     
103.         return ret;
     
104. }
     
105. 
     
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.                 }
     
116.                
     
117.                 memcpy(databak,data,i*sizeof(DWORD));
     
118.                 mySort1(data,i);
     
119.                
     
120.                 if ( !checkArray(data,i) )
     
121.                 {
     
122.                         printf("error\n");
     
123.                        
     
124.                         printf("Before sort\n\t");
     
125.                         printArray(databak,i);
     
126. 
     
127.                         printf("After sort\n\t");
     
128.                         printArray(data,i);
     
129.                         break;
     
130.                 }
     
131.         }
     
132. }
     
133. 
     
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<j)
#                 {
#                         t=p[ i ];
#                         p[ i ]=p[j];
#                         p[j]=t;
#                 }
这里因为没有进行一次i++和j--，所以下次循环的时候又需要在当前位置再判断一次，所以造成了判断次数的增加！（我最开始也是这样做的，呵呵，后来单步跟踪的时候发现这里有多余的判断，所以在他们交换值完毕的时候立即进行了一次i++和j--，以便下次循环不用再判断了）
您的这段写得比我简洁，学习了！
#                 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

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