.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 { 9int n, i, j, k;10int max_val;11vector<vector<int> > rad;1213n = (int)v.size();14if (n <= 1) {15 return;16}1718// This algorithm works for negative integers.19max_val = abs(v[0]);20for (i = 1; i < n; ++i) {21 max_val = max(abs(v[i]), max_val);22}2324int exp = 1;25while (max_val / exp >= 10) {26 exp *= 10;27}2829rad.resize(19);30int iexp = 1;31while (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}51rad.clear();52 }53 54 int main()55 {56vector<int> v;57int n, i;5859while (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}7071return 0;72 }
