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

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 对核心部分进行了优化，消除了潜在的错误。

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;
9. if ( mask<=0)
10. return ;
12. if (i>=j)
13. return;
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--;
22. if (i<j)
23. {
24. t=p[ i ]; p[ i ]=p[j]; p[j]=t;
25. i++;
26. }
27. }
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. }
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写代码还真是认真啊！