# 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
付翔 阅读(151)
评论(0) 编辑 收藏 引用 所属分类:
ACM 数据结构 、
linux 及 c相关 、
排序