基数排序（vector实现）

怼烎@ 2023-02-11 03:13 11阅读 0赞

时间限制:1000MS 代码长度限制:10KB

题型: 编程题 语言: G++;GCC

## Description ##

用函数实现基数排序，并输出每次分配收集后排序的结果

## 输入格式 ##

第一行：键盘输入待排序关键的个数n  
第二行：输入n个待排序关键字，用空格分隔数据

## 输出格式 ##

每行输出每趟每次分配收集后排序的结果，数据之间用一个空格分隔

## 输入样例 ##

10  
278 109 063 930 589 184 505 069 008 083

## 输出样例 ##

930 063 083 184 505 278 008 109 589 069  
505 008 109 930 063 069 278 083 184 589  
008 063 069 083 109 184 278 505 589 930

**解题思路：直接使用vector容器来实现，没必要使用链表。注意输出样例中是位数较少时，前面补零达到指定长度，我们就用头文件里的格式输出控制符就可以了。**

**参考代码：**

#include<iostream>
    #include<algorithm>
    #include<iomanip>
    #include<vector>
    using namespace std;
    vector<int> pocket[10];//定义动态数组的数组
    int pow(int x,int y)
    { 
    	int i,result=1;
    	for(int i=1;i<=y;i++)
    	result*=x;
    	return result;
    	
    }
    void print(int a[],int n,int t) 
    { 
    	for(int i=1;i<=n;i++)
    	cout<<setw(t)<<setfill('0')<<a[i]<<' ';
    	cout<<endl;
    }
    void RadixSort(int a[],int n,int t)//数组，元素个数，要放进袋子的次数 
    { 
    	int i,j,k,x;
    	for(i=1;i<=t;i++)//从右到左的第i位 
    	{ 
    		for(j=1;j<=n;j++)//放进相应的口袋 
    		{ 
    		    x=a[j]/pow(10,i-1)%10;//放置的口袋的编号 
    			pocket[x].push_back(a[j]);
    		}
    		x=1;
    		for(k=0;k<10;k++)//从袋子中再拿出来 
    		{ 
    			for(j=0;j<pocket[k].size();j++)
    	    	a[x++]=pocket[k][j];
    		    pocket[k].clear();//清空袋子 
    		}
    		 print(a,n,t);
    	}
    }
    int main()
    { 
    	int i,n,maxlen=0,t=0,a[1000];
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{ 
    		cin>>a[i];
    		maxlen=max(maxlen,a[i]);
    	}
    	while(maxlen)//求趟数
    	{ 
    		maxlen/=10;
    		t++;
    	 }
    	 RadixSort(a,n,t);
    	 return 0;
     }