C语言基本排序算法之桶式排序实例
本文实例讲述了C语言基本排序算法之桶式排序。分享给大家供大家参考,具体如下:
桶式排序是对一个有n个整型元素的数组a[n],其中对任意i,0<=a[i]<=m的特殊排序算法。
可以对n==m,n!=m分别处理。写代码时需要注意的的是a[i]是访问第i-1个元素,而非第i个。
/************************************************************************************/ /*Bucket_Sort.h桶式排序算法*/ /*问题:对一个有n个整型元素a[0],a[1],…,a[n-1]的数组排序,其中0<=a[i]<=m,任意i*/ /*程序:运行时间为O(m+n),辅助空间为O(m)*/ /*当n=m时特殊处理,运行时间为O(N),辅助空间为O(1)*/ /************************************************************************************/ #include/*m!=n*/ voidBucket_Sort_m(int*a,intn,intm) { std::vector temp(m,0); inti; for(i=0;i!=n;++i)//遍历a[] ++temp[a[i]-1];//如果有对应于下标的值,标记为1,否则为0 i=0; for(intj=1;j<=m;++j)//遍历temp向量 if(temp[j-1])a[i++]=j; temp.clear(); } /*m==n*/ /*最后的结果是a[i-1]=i*/ voidBucket_Sort(int*a,intn) { for(inti=1;i<=n;++i) { while(a[i-1]!=i) { inttemp=a[a[i-1]-1]; a[a[i-1]-1]=a[i-1]; a[i-1]=temp; } /*伪代码:如果假设可以通过a[i]访问数组的第i个元素,而不是第i-1个*/ /*while(a[i]!=i) { inttemp=a[a[i]]; a[a[i]]=a[i]; a[i]=temp; } */ } }
希望本文所述对大家C语言程序设计有所帮助。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。