C++数据结构--队列的应用--基数排序

缺乏、安全感 2021-12-07 11:17 292阅读 0赞

**Example:对数组91,6,85,15,92,35,30,22,39进行基数排序  
对个位进行排序后，10个队列中记录如下图  
![20130729152615421][]  
  
  
从所有队列中依次收集元素得到：30 91 92 22 85 15 35 6 39  
  
  
对十位进行排序后，10个队列中记录如下图  
![20130729152729093][]  
  
  
从所有队列中依次收集元素得到：6 15 22 30 35 39 85 91 92**

**实现代码：**

**//计算10的次幂**

**int power\_10(int n)  
\{   
int res=1;  
for(int i=0;i<n;i++)  
 res\*=10;  
  
 return res;  
\}  
  
  
//把向量数组的所有元素分配到队列数组中  
void distribute(queue<int> qarr\[\],vector<int>& vec,int radix)  
\{  
  
for(int i=0;i<vec.size();i++) //从左到右依次扫描向量数组  
\{   
int index=(vec\[i\]/power\_10(radix))%10; //计算队列数组的下标,index范围\[0,9\]   
qarr\[index\].push(vec\[i\]) ;  
\}   
\}  
  
  
//把队列数组中的所有元素收回向量数组   
void collect(queue<int> qarr\[\],vector<int>& vec)  
\{   
vec.resize(0); //清空向量数组  
for(int i=0;i<10;i++) //队列数组的下标范围\[0,9\]   
\{   
while(!qarr\[i\].empty())  
\{   
vec.push\_back(qarr\[i\].front());  
qarr\[i\].pop();  
\}   
\}   
\}   
  
  
//基数排序   
void radixSort(queue<int> qarr\[\],vector<int>& vec)  
\{   
int max=0;  
for(int i=0;i<vec.size();i++) //找出向量数组中最大的数  
\{   
if(vec\[i\]>max)  
 max=vec\[i\];  
\}  
  
int count;  
while(max) //计算最大数字的位数   
\{   
max/=10;  
count++;  
\}   
  
for(int j=0;j<count;j++) //从个位到最大位数进行基数排序   
\{   
distribute(qarr,vec,j);  
collect(qarr,vec);  
  
\}  
\}  
  
  
int main()  
\{   
vector<int> vec\{91,6,85,15,92,35,30,22,39\};  
queue<int> qarr\[10\];  
radixSort(qarr,vec);  
  
for(int x:vec)  
\{   
cout<<x<<ends;  
\}  
  
return 0;  
\}  
  
  
  
  
运行结果：  
![Center][]**

[20130729152615421]: /images/20211207/da4a83e37a8e456d8fd15be919616820.png
[20130729152729093]: /images/20211207/9766539275a748efa48318fd8114d14a.png
[Center]: /images/20211207/887918ce6480495f914c36a2fe109dc7.png