- 瑞瑞爱吃桃
-
运用桶排序即可,但有局限性只能应用于整数。
自己去百度具体代码,看懂算法在自己写代码。
桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
1.N个数字(整形)
2.求出最大的数字的位数m
3.由于数字都是0到9组成,做10个桶,0到9,将N个数字依次放入桶里面
3.1 从个位数开始,从各位数字开始,将地i(i<m)为数字相同的数字,依次放入对应的桶中
3.2 从地0个桶开始,将所有桶中的数字取出,作为一个新的数字
3.2 重复上面两步,直至m为数字
4.最后排序的为从小到大的数组排序。
因为是数据排序,所以设置的桶的键值为0~9共十个桶。每次从数据的最后一个数位开始扫描,如果这个数位的值与桶的键值相等,就把这个数据放入桶内。桶可以看作是一个有序的链表,后进入的元素排在先进入的数据的后面,直到所有的数据都完成扫描,算作一次扫描。以后依次取倒数第二个扫描,按照桶的键值开始扫描,同样把数位的值与桶的键值相等的数据放入桶内。直到所有数据的最高数位也完成扫描。最后一次扫描完成,桶的键值从低到高,把这些链表串起来输出的结果就是原来数据的从小到大排序。
---------------------------------------------------------------------------------------------------
代码(来自《数据结构算法Visual.C.6.0程序集》)
void main()
{cout<<"bucketsort.cpp运行结果: ";
int array[SIZE];
cout<<"原数组: ";
srand(time(0));
for(int i=0;i<SIZE;++i)
{array[i]=rand()0;
cout<<setw(3)<<array[i];}
cout<<" ";
cout<<"排序过程演示: ";
bucketSort(array);
cout<<"排序后数组: ";
for(int j=0;j<SIZE;++j)
cout<<setw(3)<<array[j];
cout<<endl;cin.get();
}
// 桶排序算法
void bucketSort(int a[])
{int totalDigits,bucket[10][SIZE]={0};
totalDigits=numberOfDigits(a,SIZE);
for(int i=1;i<=totalDigits;++i) {
distributeElements(a,bucket,i);
collectElements(a,bucket);
//将桶数组初始化为0
if(i!=totalDigits) zeroBucket(bucket);
for(int j=0;j<SIZE;++j)
cout<<setw(3)<<a[j];
cout<<endl;}
}
//确定单下标数组的最大数的位数
int numberOfDigits(int b[],int arraySize)
{ int largest=b[0],digits=0;
for(int i=1;i<arraySize;++i)
if(b[i]>largest)
largest=b[i];
while(largest!=0) {
++digits;
largest/=10;}
return digits;
}
// 将单下标数组的每个值放到桶数组的行中
void distributeElements(int a[],int buckets[][SIZE],int digit)
{int divisor=10,bucketNumber,elementNumber;
for(int i=1;i<digit;++i)
divisor*=10;
for(int k=0;k<SIZE;++k) {
bucketNumber=(a[k]%divisor-a[k]%(divisor/10))/(divisor/10);//求取地m为数字
elementNumber=++buckets[bucketNumber][0];//buckets[bucketNumber][0] 表示桶中的数字个数
buckets[bucketNumber][elementNumber]=a[k];//放入对应的桶中
}
}
//将桶数组的值复制回原数组
void collectElements(int a[],int buckets[][SIZE])
{int subscript=0;
for(int i=0;i<10;++i)
for(int j=1;j<=buckets[i][0];++j)
a[subscript++]=buckets[i][j];
}
//将桶数组初始化为0
void zeroBucket(int buckets[][SIZE])
{for(int i=0;i<10;++i)
for(int j=0;j<SIZE;++j)
buckets[i][j]=0;}
- 再也不做稀饭了
-
运用桶排序即可,但有局限性只能应用于整数。
自己去百度具体代码,看懂算法在自己写代码。
桶排序
(Bucket
sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是
比较排序,他不受到
O(n
log
n)
下限的影响。
1.N个数字(整形)
2.求出最大的数字的位数m
3.由于数字都是0到9组成,做10个桶,0到9,将N个数字依次放入桶里面
3.1
从个位数开始,从各位数字开始,将地i(i<m)为数字相同的数字,依次放入对应的桶中
3.2
从地0个桶开始,将所有桶中的数字取出,作为一个新的数字
3.2
重复上面两步,直至m为数字
4.最后排序的为从小到大的数组排序。
因为是数据排序,所以设置的桶的键值为0~9共十个桶。每次从数据的最后一个数位开始扫描,如果这个数位的值与桶的键值相等,就把这个数据放入桶内。桶可以看作是一个有序的链表,后进入的元素排在先进入的数据的后面,直到所有的数据都完成扫描,算作一次扫描。以后依次取倒数第二个扫描,按照桶的键值开始扫描,同样把数位的值与桶的键值相等的数据放入桶内。直到所有数据的最高数位也完成扫描。最后一次扫描完成,桶的键值从低到高,把这些链表串起来输出的结果就是原来数据的从小到大排序。
---------------------------------------------------------------------------------------------------
代码(来自《数据结构算法Visual.C.6.0程序集》)
void
main()
{cout<<"bucketsort.cpp运行结果: ";
int
array[SIZE];
cout<<"原数组: ";
srand(time(0));
for(int
i=0;i<SIZE;++i)
{array[i]=rand()0;
cout<<setw(3)<<array[i];}
cout<<" ";
cout<<"排序过程演示: ";
bucketSort(array);
cout<<"排序后数组: ";
for(int
j=0;j<SIZE;++j)
cout<<setw(3)<<array[j];
cout<<endl;cin.get();
}
//
桶排序算法
void
bucketSort(int
a[])
{int
totalDigits,bucket[10][SIZE]={0};
totalDigits=numberOfDigits(a,SIZE);
for(int
i=1;i<=totalDigits;++i)
{
distributeElements(a,bucket,i);
collectElements(a,bucket);
//将桶数组初始化为0
if(i!=totalDigits)
zeroBucket(bucket);
for(int
j=0;j<SIZE;++j)
cout<<setw(3)<<a[j];
cout<<endl;}
}
//确定单下标数组的最大数的位数
int
numberOfDigits(int
b[],int
arraySize)
{
int
largest=b[0],digits=0;
for(int
i=1;i<arraySize;++i)
if(b[i]>largest)
largest=b[i];
while(largest!=0)
{
++digits;
largest/=10;}
return
digits;
}
//
将单下标数组的每个值放到桶数组的行中
void
distributeElements(int
a[],int
buckets[][SIZE],int
digit)
{int
divisor=10,bucketNumber,elementNumber;
for(int
i=1;i<digit;++i)
divisor*=10;
for(int
k=0;k<SIZE;++k)
{
bucketNumber=(a[k]%divisor-a[k]%(divisor/10))/(divisor/10);//求取地m为数字
elementNumber=++buckets[bucketNumber][0];//buckets[bucketNumber][0]
表示桶中的数字个数
buckets[bucketNumber][elementNumber]=a[k];//放入对应的桶中
}
}
//将桶数组的值复制回原数组
void
collectElements(int
a[],int
buckets[][SIZE])
{int
subscript=0;
for(int
i=0;i<10;++i)
for(int
j=1;j<=buckets[i][0];++j)
a[subscript++]=buckets[i][j];
}
//将桶数组初始化为0
void
zeroBucket(int
buckets[][SIZE])
{for(int
i=0;i<10;++i)
for(int
j=0;j<SIZE;++j)
buckets[i][j]=0;}
- 皮皮
-
要自己写,没有现成的函数。