Counting Sort 计数排序

 1 void counting_sort(A, B, k){ 2    for(i = 0 to k){ 3        c[i] = 0;   4    }//初始化 5     6    for(j = 1 to n){ 7        c[A[j]]++; 8     }//在c【j】中记录A【i】出现的次数 9     10     for(i = 1 to k){11         c[i] = c[i] + c[i-1];12     }//在c【i】中记录小于等于A【i】的元素出现的次数13 14     for(j = n to 1){15         B[c[A[i]]] = A[i];16         c[A[i]]--;    17     }    18 }

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5 const int maxn = 1000; 6  7 int a[maxn],c[100000],ans[maxn]; 8  9 void counting_sort(int l,int r,int max_k){10   for(int i = l;i <= r; i++)c[a[i]]++;11   for(int i = 0;i <= max_k; i++)c[i] = c[i] + c[i-1];12   for(int i = l;i <= r; i++){13     ans[c[a[i]]] = a[i];14     c[a[i]]--;15   }16 }17 18 int main(){19   int n,max_k = -1;20   scanf("%d",&n);21     for(int i = 1;i <= n; i++){22       scanf("%d",&a[i]);23       max_k = max(max_k,a[i]);24     }25     counting_sort(1,n,max_k);26     for(int i = 1;i <= n; i++){27       printf("%d ",ans[i]);28     29     }30 }