桶排序的ACM题目
poj 2353
Test - 4.7
Description
桶排序（bucket sort）从一个一维的待排序的正整数数组和一个二维整数数组开始，其中二维数组的行下标是从0到9，列下标是从0到n-1，n是一维数组中待排序值的个数。这个二维数组的每一行都成为一个桶。编写一个函数bucketSort，它采用一个整数数组和该数组的大小作为参数，并执行以下操作：
a）对于一维数组的每个值，根据值的个位数，将其放到桶数组的各行中。例如，97放在第7行，3放在第3行，100放在第0行。这称为“分布过程”。
b）在桶数组中逐行循环便利，并把值复制回原始数组。这称为“收集过程”。上述值在一维数组中的新次序是 100、3和97.
c）对随后的每个数位（十位、百位、千位等）重复这个过程。在第二遍排序时，100放在第0行，3放在第0行（因为3没有十位），97放在第9行。收集过程之后，一维数组 中值的顺序为100、3和97.在第三遍排序时，100放在第一行，3放在第0行，97放在第0行（在3之后）。在最 后一次收集过程后，原属数组就是有序的了。
请注意，二维桶数组的大小是被排序的整数数组大小的10倍。这种排序方法的性能比插入排序好，但是需要非常多的内存空间。插入排序只需要额外的一个数据元素的空间。这使一个时间权衡的范例：桶排序使用的内存空间比插入排序多，但是性能比较好。这个版本的桶排序需要在每一遍排序时把所有数据复制回原始数组。另外一种方法是创建第二个二维桶数组，并在这两个桶数组间重复交换数据。
输入
第一行1个整数t，表示有t组数据。每组数据有两行：第1行为一个整数n(n不大于100)，表示数组有n个元素；第2行有n个以空格隔开的整数，即数组中每个元素的值。
输出
共t行，每行n个以空格隔开的整数，即每个数组的元素排序后的序列。
样例输入
3
3 1 2
样例输出
#include<iostream>
using namespace std;
int wei=0;
int Max=0;
int FindMax(const int * p)
{
int i=0;
while(i<wei)
{
if(p[i]>Max)
Max=p[i];
i++;
}
return Max;
}
void BucketSort(int * p,int n)
{
int ** ew=(int * *)malloc(10*sizeof(int *));
int w[10];
for(int j=0;j<9;j++)
{
ew[j]=(int *)malloc(n*sizeof(int));
}
Max=FindMax(p);//查找最大数
int i_w=0;
int temp=Max;
int i=0;
while(temp!=0)
{
i++;
temp/=10;
}/*计算出有多少位，需要循环多少次*/
int temp_i=1;
while(temp_i<=i)
{
memset(w,0,sizeof(w));//将位数初始化
int j=0;
for(/*int*/ j=0;j<n;j++)
{
int k=1;
int temp=0;
temp=p[j];
while(k<temp_i)//看哪一位,如果是第一位，那么就除以0，然后求余
{
temp/=10;
k++;
}
temp%=10;
ew[temp][w[temp]++]=p[j];
}
//还原
int z=0;
for(j=0;j<=9;j++)
{
for(int t=0;t<w[j];t++)
{
p[z++]=ew[j][t];
//cout<<p[z-1]<<' ';
}
}
temp_i++;
}
}
void Output(int *p,int n)
{
for(int i=0;i<n;i++)
{
cout<<p[i]<<' ';
}
}
int main()
{
int a[10]={1,30000,11200,10,56,123,2,33,23,16};
wei=10;
BucketSort(a,wei);
Output(a,10);
return 1;
}
评论
发表评论