# 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
付翔 閱讀(173)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構 、
linux 及 c相關 、
排序