#define _CRT_SECURE_NO_WARNINGS

#include<math.h>
#include <stdio.h>
#include <stdlib.h>

int findMaxNum(int *p, int n);
void sort2(int *p, int n, int loop);
void bucketSort3(int *p, int n);
int getLoopTimes(int num);
/*
基数排序原理：
求出数组中最大值
求出最大值的位数，作为循环轮次；
第一轮：按照个位排序
第二轮：按照十位排序
……
直到最高位
*/
testBS()
{
	int a[] = { 2, 343, 342, 1, 123, 43, 4343,3, 433, 687, 654, 3 };
	int size = sizeof(a) / sizeof(int);
	//基数排序
	bucketSort3(a, size);
	//打印排序后结果
	int i;
	for (i = 0; i < size; i++)
	{
		printf("%d\n", a[i]);
	}

}
//基数排序
void bucketSort3(int *p, int n)
{
	//获取数组中的最大数
	int maxNum = findMaxNum(p, n);
	//获取最大数的位数，次数也是再分配的次数。
	int loopTimes = getLoopTimes(maxNum);
	int i;
	//对每一位进行桶分配
	for (i = 1; i <= loopTimes; i++)
	{
		sort2(p, n, i);
	}
}
//获取数字的位数
int getLoopTimes(int num)
{
	int count = 1;
	int temp = num / 10;
	while (temp != 0)
	{
		count++;
		temp = temp / 10;
	}
	return count;
}
//查询数组中的最大数
int findMaxNum(int *p, int n)
{
	int i;
	int max = 0;
	for (i = 0; i < n; i++)
	{
		if (*(p + i) > max)
		{
			max = *(p + i);
		}
	}
	return max;
}
//将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
void sort2(int *p, int n, int loop)
{
	//建立一组桶此处的20是预设的根据实际数情况修改
	int buckets[10][12] = {0};
	//求桶的index的除数
	//如798个位桶index=(798/1)%10=8
	//十位桶index=(798/10)%10=9
	//百位桶index=(798/100)%10=7
	//tempNum为上式中的1、10、100
	int tempNum = (int)pow(10, loop - 1);
	int i, j;
	for (i = 0; i < n; i++)
	{
		int row_index = (*(p + i) / tempNum) % 10;
		for (j = 0; j < 12; j++)
		{
			if (buckets[row_index][j] == 0)
			{
				buckets[row_index][j] = *(p + i);
				break;
			}
		}
	}
	//将桶中的数，倒回到原有数组中
	int k = 0;
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < 12; j++)
		{
			if (buckets[i][j] != 0)
			{
				*(p + k) = buckets[i][j];
				buckets[i][j] = 0;
				k++;
			}
		}
	}
}

int main()
{
	testBS();

	system("pause");
}