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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。