本文共 953 字，大约阅读时间需要 3 分钟。
#includeusing namespace std;typedef long long LL;int a[100000];int getN(int a[],int n){ //找出最大的位数 LL ma = a[0]; for(int i = 1; i < n; ++i){ if(a[i] > ma){ ma = a[i]; } } int cnt = 0; while(ma > 0){ ma /= 10; ++cnt; } return cnt;}void radixSort(int a[],int n) { int len = getN(a,n); int count[10]; int base = 1; int *tmp = (int*)malloc(sizeof(int)*n); if(!tmp) return; for(int i = 0; i < len; ++i){ for(int j = 0; j < 10; ++j){ count[j] = 0; } for(int k = 0; k < n; ++k){ ++count[a[k]/base%10]; } for(int j = 1; j < 10; ++j){ count[j] =count[j] + count[j-1]; } for(int k = n-1; k >= 0; --k){ //注意这里需要逆序收集元素 否则错误 tmp[--count[(a[k]/base)%10]] = a[k]; } for(int k = 0; k < n; ++k){ a[k] = tmp[k]; } base *= 10; } }int main() { int n; cin >> n; for(int i = 0; i < n; ++i){ cin >> a[i]; } radixSort(a,n); for(int i = 0; i < n; ++i){ cout << a[i] << " "; } return 0; }
转载地址：http://vrimi.baihongyu.com/