快排代码:基2快排原理和代码

基2快排实际上是基数排序它速度特别快是O(n)级所以偶叫他基2快排 :)



它基本原理是桶排不过大家想必知道桶排有多么吃内存....想要排32位整数需要4GBBUFFER....恐怖吧~所以只好以时间换空间~减少空间开销多画点时间了基数排序其实就是多趟桶排



什么是基数排序？基数大家都应该知道....比如说10进制基数就是10我们比较10进制数是如何比较？肯定是先看最高位然后向个位发展...基数排序和这个原理是样不过我们比较喜欢选择用2整数次幂作为基数~除以2整数次幂时候可以用位移~



OK废话不多说来说下基2快排思路(以下都是伪代码)



我们假设入口传入了原src以及长度N那么肯定要开个计数器(毕竟是基于桶排嘛~) count还有个临时temp[N]我们以2^8作为基数排序32位整数为例



for 4 次(i=0,1,2,3)
{
ZeroMemory(count); //显然是要清空计数器
memcpy(temp,src,n*4)；//以后操作都是对temp操作最后以temp为原拷贝回src去
For k=0 to N-1
{
count[(temp[k]>>(8*i))&0xFF];//在这里进行桶排
}



entry_po=0;//这个变量记录了每个计数器数据经过排列后在中位置



for k = 0 to 256
{
_temp=count[k];
count[k]=entry_po; //把相应数据个数变成了相应数据在中位置
entry_po_temp; //显然是要把BASE ENTRY_POINT推后~
}



for k=0 To N
src[count[(temp[k]>>(8*i))&0xFF]]=temp[k]; //这里有点难理解这个语句意思是根据中这个数字相应“位”(相当于10进制个位、十位)位置把这个数字拷贝回原中这样就对这个“位”排过序了



}



最后送上例子代码……可能有错……而且大家可以看到偶语文水平确实8行欢迎大家拍偶砖


\" border=0>本主题包含附件: 文档下载

延伸阅读

• 2010-12-9-- html代码示例,PHP网站安装程序制作的原理、步骤、注意事项和示例代码
• 2009-2-12-- 代码编译器:环境变量和选择性代码编译