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

silitex

很不幸，你的修改时错的，你增加i++,j--这行代码，然后运行一下我的测试程序就明白了。
liangbch 发表于 2009-11-4 12:18

厄，呵呵，在您的代码上如果仅仅增加i++,和j--这两行，是还不行的（当然，这也是我没有表达清楚意思，抱歉）。所以如果要解决不多判断一次，又让这个代码运行不出错，需要再另外处理一下，我的代码就进行了这样的一个处理。当然，话说回来，是我太追求细节了，为了尽量减少判断次数及移动次数，进行了单步跟踪及修正（自嘲）。
非常高兴和您的沟通！

silitex

看了一下周建钦写的那篇文章，本质上和我的代码是一致的。
liangbch 发表于 2009-11-4 12:31

是的，不过周在描述时间复杂度时疏漏了，应该为O（nlogm）（进行了n长度的logm次扫描），当然空间复杂度就是O（logm）（因为递归深度为logm）了

gxqcn

两位对此均有研究，探讨就可以更深入了。

〇〇

继续学习

liangbch

21# silitex

对核心部分进行了优化，消除了潜在的错误。

1. 
   
2. //bit 排序核心算法，这是一个递归函数
   
3. void bitSort(DWORD *p, int begin, int end, DWORD mask )
   
4. {
   
5.         int i=begin;
   
6.         int j=end;
   
7.         DWORD t;
   
8.        
   
9.         if ( mask<=0)
   
10.                 return ;
    
11. 
    
12.         if (i>=j)
    
13.                 return;
    
14.        
    
15.         while (i<j)
    
16.         {
    
17.                 while ( (p[ i ] & mask) ==0 && i<=j)
    
18.                         i++;
    
19.                 while ( (p[j] & mask) >0 && i<=j)
    
20.                         j--;
    
21.                
    
22.                 if (i<j)
    
23.                 {
    
24.                         t=p[ i ];        p[ i ]=p[j]; p[j]=t;
    
25.                         i++;
    
26.                 }
    
27.         }
    
28.        
    
29.         if (j<begin || i>end)        //没有左半部分,或者右半部分
    
30.         {
    
31.                 bitSort(p,begin,end,mask/2);
    
32.         }
    
33.         else  
    
34.         {
    
35.                 bitSort(p,begin,i-1,mask/2);
    
36.                 bitSort(p,i,end,mask/2);
    
37.         }
    
38. }

复制代码

liangbch

周建钦写的代码，变量名称和数据类型稍有改动
//周建钦写的排序函数

1. void zjq_sort(DWORD *a,int low,int high,DWORD mask)
   
2. {
   
3.         int i,j;
   
4.         DWORD x; // x为临时变量
   
5.         i=low;
   
6.         j=high;
   
7.         while(i<j)
   
8.         {
   
9.                 while ( (a[j] & mask) && i<j )  j--;
   
10.                 while ( (a[i] & mask)==0 && i<j) i++;
    
11.                 if(i<j)
    
12.                 {
    
13.                         x=a[j];
    
14.                         a[j]=a[i];
    
15.                         a[i]=x;
    
16.                 }
    
17.                 else
    
18.                 {
    
19.                         if( a[j] & mask) i--;
    
20.                         else        j++;
    
21.                         break;
    
22.                 }
    
23.         }
    
24. 
    
25.         if(mask>1)
    
26.         {
    
27.                 if(low<i)  zjq_sort(a,low,i,mask/2);
    
28.                 if(j<high) zjq_sort(a,j,high,mask/2);
    
29.         }
    
30. }

复制代码

silitex

，学习了！liangbch写代码还真是认真啊！