网页功能: 加入收藏 设为首页 网站搜索  
基2快排原理与代码
发表日期:2006-09-03作者:[转贴] 出处:  

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

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

什么是基数排序?基数大家都应该知道....比如说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_point=0;//这个变量记录了每个计数器数据经过排列后在数组中的位置

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

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

}

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


本主题包含附件: sf_2005121161838.rar (487bytes)

我来说两句】 【加入收藏】 【返加顶部】 【打印本页】 【关闭窗口
中搜索 基2快排原理与代码
本类热点文章
  A*寻路算法(For 初学者)
  A*寻路初探 GameDev.net
  用有限状态机实现的迷宫求解
  计算机中随机数的产生
  精美的随机数生成器程序
  即时战略游戏中如何协调对象移动
  计算几何算法概览
  飞行射击游戏中的碰撞检测
  电脑AI浅谈
  五子棋算法探讨
  小谈网络游戏同步
  五子棋算法
最新分类信息我要发布 
最新招聘信息

关于我们 / 合作推广 / 给我留言 / 版权举报 / 意见建议 / 广告投放  
Copyright ©2003-2024 Lihuasoft.net webmaster(at)lihuasoft.net
网站编程QQ群   京ICP备05001064号 页面生成时间:0.00379