求k桶法排序的C语言代码k桶法:k桶法有两个主要步骤:分桶,整合.分桶:把n个数依次放入k个桶中,除了第k个桶外,放入前k-1个桶中的数都要求后一个大于前一个.分桶的具体规则如下:第1个数
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/02 17:59:30
![求k桶法排序的C语言代码k桶法:k桶法有两个主要步骤:分桶,整合.分桶:把n个数依次放入k个桶中,除了第k个桶外,放入前k-1个桶中的数都要求后一个大于前一个.分桶的具体规则如下:第1个数](/uploads/image/z/1672332-60-2.jpg?t=%E6%B1%82k%E6%A1%B6%E6%B3%95%E6%8E%92%E5%BA%8F%E7%9A%84C%E8%AF%AD%E8%A8%80%E4%BB%A3%E7%A0%81k%E6%A1%B6%E6%B3%95%EF%BC%9Ak%E6%A1%B6%E6%B3%95%E6%9C%89%E4%B8%A4%E4%B8%AA%E4%B8%BB%E8%A6%81%E6%AD%A5%E9%AA%A4%EF%BC%9A%E5%88%86%E6%A1%B6%2C%E6%95%B4%E5%90%88.%E5%88%86%E6%A1%B6%EF%BC%9A%E6%8A%8An%E4%B8%AA%E6%95%B0%E4%BE%9D%E6%AC%A1%E6%94%BE%E5%85%A5k%E4%B8%AA%E6%A1%B6%E4%B8%AD%2C%E9%99%A4%E4%BA%86%E7%AC%ACk%E4%B8%AA%E6%A1%B6%E5%A4%96%2C%E6%94%BE%E5%85%A5%E5%89%8Dk-1%E4%B8%AA%E6%A1%B6%E4%B8%AD%E7%9A%84%E6%95%B0%E9%83%BD%E8%A6%81%E6%B1%82%E5%90%8E%E4%B8%80%E4%B8%AA%E5%A4%A7%E4%BA%8E%E5%89%8D%E4%B8%80%E4%B8%AA.%E5%88%86%E6%A1%B6%E7%9A%84%E5%85%B7%E4%BD%93%E8%A7%84%E5%88%99%E5%A6%82%E4%B8%8B%EF%BC%9A%E7%AC%AC1%E4%B8%AA%E6%95%B0)
求k桶法排序的C语言代码k桶法:k桶法有两个主要步骤:分桶,整合.分桶:把n个数依次放入k个桶中,除了第k个桶外,放入前k-1个桶中的数都要求后一个大于前一个.分桶的具体规则如下:第1个数
求k桶法排序的C语言代码
k桶法:k桶法有两个主要步骤:分桶,整合.
分桶:把n个数依次放入k个桶中,除了第k个桶外,放入前k-1个桶中的数都要求后一个大于前一个.分桶的具体规则如下:
第1个数放入第一个桶内,第2个数若大于第一个桶中的数(即第一个数)则放入第一个桶内,否则放入第二桶内,以此类推.设现要将第j个数放入某桶中,先从第一个桶试起,若第j个数大于当前第一个桶中最后一个数,则放入第一个桶中,否则试放第二个桶,以此类推,若前k-1个桶都不能放入,则直接放入第k个桶.
整合:把k个桶中当前排在最前面的数中最小者依次放回到原数组中,直到k个桶空为止.
若整合后的数组已排好序,则算法停止,否则重新分桶、整合,直到排好序为止.
对于k桶法要求可以改变k的值,并通过试验观察k的影响.
求k桶法排序的C语言代码k桶法:k桶法有两个主要步骤:分桶,整合.分桶:把n个数依次放入k个桶中,除了第k个桶外,放入前k-1个桶中的数都要求后一个大于前一个.分桶的具体规则如下:第1个数
#include <stdio.h> //for printf
#include <stdlib.h> //for srand rand
#include <time.h> //for time
#include <memory.h> //for memset
#define M 99
#define N 25
#define K 4
int a[N]; //待排序数组
int b[K][N]={0}; //桶
int c[K]={0}; //分桶时,用来记录每个桶中数据个数
int d[K]={0}; //组合时,用来记录已经处理数据个数
void print(char *pre,int a[], int n)
{
int i;
printf("%s", pre);
for(i=0;i<n;i++) printf("%3d", a[i]);
printf("\n");
}
void FillA()
{
int i,j,t,x[M];
for(i=0;i<M;i++) x[i]=i+1;
for(i=0;i<M;i++) {j=rand()%M;t=x[i];x[i]=x[j];x[j]=t;}
for(i=0;i<N;i++) a[i]=x[i];
print("--:", a, N);
}
int bucket(int a[], int n, int k)
{
int i,j,flag=0;
//分桶
for(i=0;i<N;i++)
{
for(j=0;j<k-1;j++)
{
if(c[j]==0 || b[j][c[j]-1]<a[i])
{
b[j][c[j]++]=a[i];
break;
}
}
if(j>=k-1) b[j][c[j]++]=a[i];
}
//输出当前桶中的数据
for(i=0;i<k;i++) print(" :",b[i], c[i]);
//组合
for(i=0;i<N;i++)
{
int min=M,mink=0;
for(j=0;j<k;j++)
{
if(d[j]<c[j] && b[j][d[j]]<min)
{
min=b[j][d[j]];
mink=j;
}
}
a[i]=min;
d[mink]++;
//更新排序完成标识flag
if(flag==0 && i>0 && a[i]<a[i-1]) flag=1;
}
//输出组合后的数组
print("--:", a, N);
return flag;
}
int main()
{
srand(time(0));
FillA();
do
{
memset(b,0,N*K*sizeof(int));
memset(c,0,K*sizeof(int));
memset(d,0,K*sizeof(int));
} while(bucket(a,N,K));
return 0;
}
运行结果截图: