第七章#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;
}