首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第六章“排序”——基数排序

《数据结构与算法分析：C语言描述》复习——第六章“排序”——基数排序

2024-07-08 12:27:44   215人阅读

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 }

 


联系
我们