ALDS1_6_A:桶排序算法详解与实现

题目链接：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A

输入：一个数组

输出：计数排序后的数组

思路：新开一个数组，输入数组的元素的值作为新数组的下标志，输入数组相同元素出现过的次数作为新数组的value

排序时，把新数组C递加，C[n+1]=C[n+1]+C[n]；得到的C[n]里面存的是排序后，该元素的位置。需要注意的是，相同的元素会获得相同的位置，需要进行修正。

代码如下：

#include
#include
#include
using namespace std;
int A[2000010],B[2000010];
int C[100010];int main (){int n;cin>>n;for(int i=0;i<100000;i++) C[i]=0;for(int i=0;i>A[i+1];C[A[i+1]]++;}for(int i=1;i<100000;i++) C[i]+=C[i-1];for(int i=1;i<=n;i++){B[C[A[i]]]=A[i];C[A[i]]--;}for(int i =1;i<=n;i++) cout<}

按照自己之前的理解，也可以直接按下面这样写：

在获取C[n]之后，不把新数组C递加，直接从小到大遍历，按次数输出，代码如下：

#include
#include
#include
using namespace std;
int A[2000010];
int C[100010];int main (){int n;cin>>n;for(int i=0;i<100000;i++) C[i]=0;for(int i=0;i>A[i];C[A[i]]++;}int flag=0;for(int i=0;i<100000;i++){for(int j=C[i];j>0;j--) if(flag) {cout<<" "<}

错点：

1.修正的过程这样完成

B[C[A[i]]]=A[i];
C[A[i]]--;