排序算法--桶排序（基数排序）

排序算法–桶排序（基数排序）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//获取最大位数的位数
int GetMaxNumFin(int arr[],int len)
{
	//0--个位 1--十位  2--百位......
	int max=-1;
	int i=0;
	int count=0;
	for(;i<len;i++)
	{
		if(arr[i]>max)
		{
			max=arr[i];
		}
	}
	while(max!=0)
	{
		max=max/10;
		count++;
	}
	return count;
}

int GetFinNumber(int val,int pos)
{
	//给出数字，获取对应位数的数字
	return val/(int)(pow(10.0,pos))%10;
}
void Radix(int arr[],int len,int fin)
{
	//放入数据进入桶
	int *bucket[10];
	int i=0;
	for(;i<10;i++)
	{
		bucket[i]=(int *)malloc(sizeof(int)*len-1);
	}
	int finnum;//代表位数的数字
	int count[10]={0};//每个桶中当前可插入元素的下标，当前桶中的元素
	//0---
	//1---
	for(i=0;i<len;i++)
	{
		finnum=GetFinNumber(arr[i],fin);
		bucket[finnum][count[finnum]]=arr[i];
		count[finnum]++;
	}
	int arrindex=0;
	int bucketindex=0;
	for(i=0;i<10;i++)
	{
		//从桶中拿数据
		bucketindex=0;
		while(count[i]!=0)
		{
			arr[arrindex]=bucket[i][bucketindex];
			bucketindex++;
			arrindex++;
			count[i]--;
		}
	}
	for(i=0;i<10;i++)
	{
		free(bucket[i]);
	}
}
void RadixSort(int arr[],int len)
{
	//基数排序
	int MaxFin=GetMaxNumFin(arr,len);
	int i=0;
	for(;i<MaxFin;i++)
	{
		Radix(arr,len,i);
	}
}
void show(int arr[],int len)
{
	int i=0;
	for(;i<len;i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}
int main()
{
	int arr[]={15,3,2,43,46,75,12,4,235,45,7};
	int len=sizeof(arr)/sizeof(int);
	show(arr,len);
	RadixSort(arr,len);
	show(arr,len);
	return 0;
}