频道栏目
首页 > 资讯 > 其他综合 > 正文

可以进行原地排序的计数排序

13-11-29        来源:[db:作者]  
收藏   我要投稿
如题,算法导论上给出的计数排序需要额外申请O(n)的空间来存储排好序的结果。
 
在算法导论(第二版)8-2思考题中,提出能否只需要O(k)的空间复杂度,对计数排序进行修改,实现原地排序。
 
 
下面给出原计数排序的伪代码
 
T *counting_sort(T a[],int n,int k)
 
{
 
int *c=new int[k+1];
 
T *b=new T[n];
 
int i;
 
for(i=0;i<=k;i++)
 
c[i]=0;
 
for(i=0;i<n;i++)
 
c[a[i].key]+=1;
 
for(i=1;i<=k;i++)
 
c[i]+=c[i-1];
 
for(i=n-1;i>=0;i--)
 
{
 
1: b[c[a[i].key]-1]=a[i];
 
c[a[i].key]--;
 
}
 
}
 
通过要进行修改,使得满足原地排序的条件,就需要把b数组去掉,上述代码标号1处就得需要改成swap操作,即swap(a[c[a[i].key-1]],a[i]);
 
但是,这样做就会有一个问题,交换过之后,如果在扫描过程中再次遇到交换过已经放入正确位置元素,怎么判断此元素已经被交换过,并且放入了正确的位置呢?
 
这里给出一个判断条件,我们需要一个额外的数组c_sav[0..k],它保存了进行交换前的最原始的数组c的元素。
 
假设对于下标为i的元素,a[i],if c[a[i].key]<=i and i<=c_sav[a[i].key],则说明a[i]已经被放入了正确的位置i处。
 
对于这个判断定理,我们来证明它:
 
假设对于任意下标为i的元素,a[i]没有被放入正确的位置,那么a[i]应该被放入位置下标为j的位置。则j应该满足条件,j=c[a[i].key],当讲a[i]放到a[j]位置时,c[a[j].key]做减1操作,此时j>=c[a[j].key] and j<=c_sav[a[j].key],证毕。
 
 
原地排序的计数排序伪代码如下:
 
 
T *counting_sort(T a[],int n,int k)
 
{
 
int *c=new int[k+1];
 
int *c_sav=new int[k+1];
 
int i;
 
for(i=0;i<=k;i++)
 
{
 
c[i]=0;
 
c_sav[i]=0;
 
}
 
for(i=0;i<n;i++)
 
{
 
c[a[i].key]+=1;
 
c_sav[a[i].key]+=1;
 
}
 
for(i=1;i<=k;i++)
 
{
 
c[i]+=c[i-1];
 
c_sav[i]+=c_sav[i-1];
 
}
 
i=n-1;
 
while(i>=0)
 
{
 
if(i>=c[a[i].key-1]&&i<=c_sav[a[i].key-1])
 
i--;
 
else{
 
c[a[i]]--;
 
swap(a[c[a[i].key-1]],a[i]);
 
}
 
}
 
for(i=n-1;i>=0;i--)
 
{
 
b[c[a[i].key]-1]=a[i];
 
c[a[i].key]--;
 
}
 
}
 
 
相关TAG标签
上一篇:台积电:绝大多数7nm客户都会转向6nm_IT新闻_博客园
下一篇:最后一页
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站