付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
# include<stdio.h>
# include
<stdlib.h>
# include
<iostream>
# define DEBUG 
1
const int N  = 100;
/* 适合输入范围比较小的 确切的说应该是小于10万的数据量  才适用 */
int count_qsort(int input_array[],int n)
{
    
// int result_array[n] ; 这样分配不对 
    int *result_array,*temp_array;
    
//int result_array[N] = {0},temp_array[N] = {0};
    result_array = (int *)malloc(sizeof(int)*n);
    temp_array 
=  (int *)malloc(sizeof(int)*N);
    
int i,j;
    
    memset(result_array,
0,sizeof(result_array)*n);//memset(result_array,0,sizeof(result_array)) 很习惯的ACM的写法 但是因为
    
//ACN经常是开静态 或者全局数组 sizeof 可以得到全部的大小 但是 这里result 是指针的话 就不一样了 得到的只是一个指针的大小
    
// 即四个字节 很久没有写代码 一写就出错 TMD 
    memset(temp_array,0,sizeof(temp_array)*N);
    
for(i = 0 ; i < n; i ++)
    {
        j 
= input_array[i];
        temp_array[j] 
++;
    }
    
for(i = 1; i < N; i ++)/*得到 某一值的最大位置*/
        temp_array[i] 
+= temp_array[i-1];

    
for(i = n-1; i >= 0 ; i -- )
    {
        
if(temp_array[input_array[i]])
        {
            result_array[ temp_array[ input_array[i]] 
-1= input_array[i];
            temp_array[input_array[i]] 
--;
        }
    }

    
for(i = 0 ; i < n; i ++)
        input_array[i] 
= result_array[i];
    
return 0;
}
int main()
{
    
int data[N];
    
int num,i;
#ifdef DEBUG
    scanf(
"%d",&num);
    
for(i = 0; i < num; i ++)
        scanf(
"%d",&data[i]);
    count_qsort(data,num);
    
for(i = 0 ; i < num ;i ++)
        printf(
"%d ",data[i]);
#endif
    
return 0;
}
posted on 2010-09-25 00:16 付翔 阅读(165) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构linux 及 c相关 排序

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



<2010年4月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜