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 }

?

轉載于:https://www.cnblogs.com/zhuli19901106/p/3792090.html

總結

以上是生活随笔為你收集整理的《数据结构与算法分析：C语言描述》复习——第六章“排序”——基数排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。