2014.06.17 06:42
简介：
基数排序是一种非比较算法，通过多轮的分配与合并来排序整个数组。应用范围比较窄，根据Wikipedia的说法，它只适合整数排序。
描述：
基数排序和桶排序有点类似，都是将元素按照特定依据分配到多个桶中。但它和桶排序的区别，在于它要进行不止一次的分配与合并。每次分配元素所用的“依据”是元素的某一位数字，分配按照由低位到高位的顺序进行。教材中和我搜到的一些资料中都只给出了整数数组的示例，我也暂时没想清楚基数排序能否应用到其他数据类型上。
排序：
1 // My implementation for radix sort. 2 #include <algorithm> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 void radixSort(vector<int> &v) 8 { 9 int n, i, j, k; 10 int max_val; 11 vector<vector<int> > rad; 12 13 n = (int)v.size(); 14 if (n <= 1) { 15 return; 16 } 17 18 // This algorithm works for negative integers. 19 max_val = abs(v[0]); 20 for (i = 1; i < n; ++i) { 21 max_val = max(abs(v[i]), max_val); 22 } 23 24 int exp = 1; 25 while (max_val / exp >= 10) { 26 exp *= 10; 27 } 28 29 rad.resize(19); 30 int iexp = 1; 31 while (true) { 32 for (i = 0; i < n; ++i) { 33 rad[v[i] / iexp % 10 + 9].push_back(v[i]); 34 } 35 36 k = 0; 37 for (i = 0; i < 19; ++i) { 38 int n2 = (int)rad[i].size(); 39 for (j = 0; j < n2; ++j) { 40 v[k++] = rad[i][j]; 41 } 42 rad[i].clear(); 43 } 44 45 if (iexp == exp) { 46 break; 47 } else { 48 iexp *= 10; 49 } 50 } 51 rad.clear(); 52 } 53 54 int main() 55 { 56 vector<int> v; 57 int n, i; 58 59 while (cin >> n && n > 0) { 60 v.resize(n); 61 for (i = 0; i < n; ++i) { 62 cin >> v[i]; 63 } 64 radixSort(v); 65 for (i = 0; i < n; ++i) { 66 cout << v[i] << ‘ ‘; 67 } 68 cout << endl; 69 } 70 71 return 0; 72 }