第七章#7.6基数排序

基本思想：分配+收集

也叫桶排序或箱排序

设置若干个箱子，将关键字为k的记录放入第k个箱子，然后再按序号将非空的连接

基数排序：数字是有范围的，均由0~9这十个数字组成，则只需设置，十个箱子，相继按个、十、百...进行排序

//基数排序算法
#include <bits/stdc++.h>
#define MAXSIZE 50
#define MAX_BIT_SIZE 5
using namespace std;
int arr[MAXSIZE+1]; 

int MaxBit(int arr[], int n) {//求出arr中每个元素的位数，并返回最大位数
	int maxbit=0, count;
	for (int i=1; i<=n; i++) {
		int tem=arr[i]; count=0;
		while (tem) {
			tem/=10; count++;
		}
		if (count>maxbit) maxbit=count;
	}
	return maxbit;
} 

int PickBit(int num, int w) {//从个位开始为1位，十位为2位
	for (int i=1; i<w; i++) num/=10;
	return num%10;
}//求取num的第i位数字是什么

//定义桶类型，用于取位进行桶排序
typedef struct {
	int bit[MAX_BIT_SIZE];
	int ptr=0;//指向此时的桶盖
} Radix;

//桶排序算法
void RadixSort(int n) {
	int m=MaxBit(arr, n);//arr中最大位数m
	for (int i=1; i<=m; i++) {//进行m趟桶排序，i同时表示当前是第几位（个位、十位...）
		Radix r[10];//建立0~9的桶，用于排序
		for (int j=1; j<=n; j++) {//对arr中每个元素从前向后遍历
			int b=PickBit(arr[j], i);//取当前位
			int p=r[b].ptr++;//取当前桶盖位置，并将桶盖上移一位
			r[b].bit[p]=arr[j];//向对应b位的桶中加入该元素
		}
		int f=1;
		for (int k=0; k<10; k++) {//重新从桶中取出这一趟排序的结果，并放回arr中
			for (int v=0; v<r[k].ptr; v++) {
				arr[f]=r[k].bit[v]; f++;
			}
		}
	}
}

int main() {
	int n; cin>>n;//输入数列长度
	for (int i=1; i<=n; i++) cin>>arr[i];//输入乱序数列
	for (int i=1; i<=n; i++) cout<<arr[i]<<' ';
	cout<<endl;//输出乱序数列
	RadixSort(n);//进行桶排序
	for (int i=1; i<=n; i++) cout<<arr[i]<<' ';
	cout<<endl;//输出顺序数列
	return 0;
}