原理
基数排序是一种非比较的排序算法,它是以桶排序为基础的。
这样排序的原因是因为觉得按高位排序,高位影响大,做出的变动更多,而从低位开始排序,低位影响小,做出的变动小。
#include <iostream> #include <vector> #include <string> using namespace std; //最大位数 int maxbit(vector<int> arr){ int len=0; for(auto x:arr){ int count=0; while(x>0){ x/=10; c++; } if(len<count) len=count; } return len; } /*基于int型数组的基数排序简单实现*/ void radixsort(vector<int> &arr){ const buckets_number=10; vector<vector<int> > buckets(10);//10个桶,每个桶是vector<int> int len = maxbit(arr); int r=1; for(int i=0;i<len;i++){ for(int x:arr){ int tmp=x/r; int index = tmp%buckets_number; buckets[index].push_back(x); } int i=0; for(auto bucket:buckets){ for(int x:bucket){ arr[i] = x; i++; } bucket.clear(); } r = r*10; } } /**************************************************************/ //字符 void radixsort(vector<string> &arr,int stringlen){ const int buckets_number=256; vector<vector<int> > buckets(buckets_number); for(int i=stringlen-1;i>=0;i--){ for(string s:arr){ buckets[s[i]].push_back(s); } int idx=0; for(auto bucket:buckets){ for(string s:bucket){ arr[idx++] = s } bucket.clear(); } } }