MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
 from  -> introdution to algorithms

原理简单,稳定性高,有应用条件 即 : n个输入元素都是在0 - k之间的整数,当k = O(n)时, 计数排序的时间为O(n).



#include <stdio.h>
#include 
<string.h>
const int _ = 0x7fffffff;
int a[100], n, out[100];
int c[100];
int main(){
    freopen(
"count_sort.in""r", stdin);
    freopen(
"count_sort.out""w", stdout);
    
int i, k;
    
while(scanf("%d"&n) != -1){
        k 
= -_;
        memset(c, 
0sizeof(c));
        
for(i = 0; i < n; i++){
            scanf(
"%d"&a[i]);
            
if(a[i] > k)k = a[i];
            c[a[i]]
++//初始化<=自己的元素个数为1。
        }
        
for(i = 1; i <= k; i++)c[i] += c[i - 1];//c中存放整个数列中小于等于自己的元素的个数。
        for(i = 0; i < n; i++){
            
out[c[a[i]]] = a[i];//放到相应的位置上 比如 有 5个元素小于等于自己(包含自己),那么,这个元素应该排在第五位
            c[a[i]]--;//计数器 - 1
        }
        
for(i = 1; i <= n; i++)printf("%d "out[i]);
        puts(
"");
    }
    
return 0;
}

posted on 2009-09-29 13:12 memorygarden 阅读(289) 评论(0)  编辑 收藏 引用 所属分类: 报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理