C++实现基数排序(Radix Sort)

最近期末课程设计,有一题要求对N个0-999的数字进行基数排序,以前并没有听说过这种排序,在百度看了相应的原理之后,动手写了以下基数排序的代码出来,特此分享给大家。
代码中使用了C++ STL的vector以及queue,以此简化实现方法。

#include<iostream>
#include<vector>
#include<fstream>
#include<ctime>
#include<queue>
using namespace std;

const int N = 1000;
vector<queue<int>> container(10); 
vector<int> orderArray;
void random(){ //随机生成数字
	srand(unsigned(time(NULL)));
	ofstream fout("out.txt");
	for(int i=0;i<N;i++){
		int num = rand()%1000;
		fout << num <<endl;
//		cout << num <<endl;
		orderArray.push_back(num);
	}
	fout.close();
}


void RadixSort(){
	for(int m = 0;m<3;m++){
		for(int i=0;i<orderArray.size();i++){
			int temp = orderArray[i];
			for(int j=0;j<m;j++) temp/=10; //取个位、十位、百位
			container[temp%10].push(orderArray[i]); //按上述位数投入相应容器
		}
		orderArray.clear(); //清空初始数组
		for(int i=0;i<10;i++){ // 将容器内的数按次序收集下来
			while(!container[i].empty()){
				orderArray.push_back(container[i].front());
				container[i].pop();
			}
		}
	}
}

void printArray(){
	ofstream fout("result.txt");
	for(int i=0;i<orderArray.size();i++){
		cout << orderArray[i] <<endl;
		fout << orderArray[i] <<endl;
	}
	fout.close();
}
int main(){
	random();
	RadixSort();
	printArray();
}

发表评论

沙发空缺中,还不快抢~