学步园

#include <iostream><br /> using namespace std;</p> <p>class CountingSort<br /> {<br /> private:<br /> int *arr;//待排序数组<br /> int *count;<br /> int *result;<br /> int length;//数组长度<br /> int max;//最大元素<br /> public:<br /> //构造函数<br /> CountingSort(int length)<br /> {<br /> max=-1;<br /> this->length=length;<br /> arr=new int[length+1];<br /> result=new int[length+1];<br /> }<br /> //输入<br /> void input()<br /> {<br /> int i=1;<br /> while(i<=length)<br /> {<br /> cin>>arr[i];<br /> if(arr[i]>max)//记录数组中最大值<br /> {<br /> max=arr[i];<br /> }<br /> i++;<br /> }<br /> count=new int[max+1];<br /> }<br /> //计数排序<br /> void countingSort()<br /> {<br /> //初始化每一个元素的数量为0<br /> for(int i=0;i<=max;i++)<br /> {<br /> count[i]=0;<br /> }<br /> //记录数组中出现的元素的个数<br /> for(int j=1;j<=length;j++)<br /> {<br /> count[arr[j]]++;<br /> }<br /> //计算小于等于1:MAX每个元素的元素数量<br /> for(int k=1;k<=max;k++)<br /> {<br /> count[k]=count[k]+count[k-1];<br /> }<br /> //根据count[],将每个元素插入到相应的位置<br /> for(int m=1;m<=length;m++)<br /> {<br /> result[count[arr[m]]]=arr[m];<br /> count[arr[m]]--;<br /> }<br /> }<br /> //打印排序后结果<br /> void display()<br /> {<br /> int i=1;<br /> while(i<=length)<br /> {<br /> cout<<result[i++]<<" ";<br /> }<br /> }<br /> };</p> <p>void main()<br /> {<br /> CountingSort test(10);//数组有10个元素<br /> test.input();//输入10个元素<br /> test.countingSort();//计数排序<br /> test.display();//打印结果<br /> }