算法导论 计数排序
计数排序的关键就在于如何处理每个元素的最终位置。在计数排序中,我们可以通过维护一个数组C[i]来记录键值为i的元素所属的位置。每次输入一个A[i],首先记录每个A[i]出现的次数C[i],然后从前向后C[i]=C[i-1]+C[i],这样可以得出值为i所在排序后新数组中的最后一个重复数的位置。计数排序的一个显然问题就是C[]数组的大小确定的问题。下面贴上我自己理解写出的代码。
#include<iostream> using namespace std; int main() { int n,i; int A[1000],B[1000],C[1000]; while(cin>>n) { for(i=1;i<=n;i++) cin>>A[i]; for(i=0;i<=n;i++) C[i]=0; for(i=1;i<=n;i++) C[A[i]]=C[A[i]]+1; for(i=1;i<=n;i++) C[i]=C[i-1]+C[i]; for(i=1;i<=n;i++) { B[C[A[i]]]=A[i]; C[A[i]]-=1; } for(i=1;i<=n;i++) cout<<B[i]<<" "; cout<<endl; } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。