给定的n个的d位数，其中每一个数位有k个可能的取值。如果对每个有效位排序采用的是稳定的计数排序算法，则时间复杂度是O(d(n+k)),空间 1 #include<iostream>
2 #include<string.h> 3 #include <algorithm> 4 using namespace std; 5 int maxbit(int data[], int n) 6 { 7 int d = 1; 8 int p = 10; 9 for (int i = 0; i < n; i++) 10 { 11 while (data[i]>=p) 12 { 13 p *= 10; 14 ++d; 15 } 16 } 17 return d; 18 } 19 void radixsort(int data[],int m) 20 { 21 int temp[10][m]; 22 int order[10]; 23 memset(temp, 0, sizeof(temp)); 24 memset(order, 0, sizeof(order)); 25 int d = maxbit(data, m); 26 27 int n = 1; 28 for(int x=0;x<d;x++)
29 { 30 int i; 31 for (i = 0; i < m; i++) 32 { 33 int lsd = (data[i] / n) % 10; 34 temp[lsd][order[lsd]] = data[i]; 35 order[lsd]++; 36 } 37 // 38 int k = 0; 39 for (i = 0; i < 10; i++) 40 { 41 if (order[i] != 0) 42 { 43 int j = 0; 44 for (j = 0; j < order[i]; j++) 45 { 46 data[k] = temp[i][j]; 47 k++; 48 } 49 } 50 order[i] = 0; 51 } 52 n *= 10; 53 } 54 } 55 int main() 56 { 57 int a[] = { 1, 2, 8, 6, 44, 88, 63, 22, 633 }; 58 int n = sizeof(a) / sizeof(a[0]); 59 for (int i = 0; i < n; i++) 60 cout << a[i] << " "; 61 cout << endl; 62 radixsort(a,n); 63 for (int i = 0; i < n; i++) 64 cout << a[i] << " "; 65 cout << endl; 66 return 0; 67 }