2020/6/15 20:45更正：
二次排序由插入排序改成递归后，在桶数为排序总数0.5倍的情况下，排序速度比快排高，如果桶数增加到1倍，还可以提高，再增加桶数速度增加不明显，甚至有些倍数还降低了。
前两天在https://bbs.bccn.net/thread-501938-1-1.html参与了桶排序讨论，今天用代码实现了下，并把它合并到我的不同排序算法比较的代码中。
经过反复优化，发现桶排序虽然属于非比较类型排序，却没有什么优势，通过不断调整桶数，观察到当桶数是被排序数的4倍时，才勉强和c qsort的排序速度相当。
当然，我的算法并不是严格意义上的非比较排序，我在二次排序中用了插入排序。现在正考虑设计一个桶数据结构，让该算法可以使二次排序通过递归调用完成，也许能够提高些速度，预计可以达到分治法排序速度，大概是c qsort的1.4倍。
下图是设置不同桶数时排序速度的变化：
下面是我的桶排序代码，欢迎提供宝贵意见：
程序代码：
二次排序由插入排序改成递归后，在桶数为排序总数0.5倍的情况下，排序速度比快排高，如果桶数增加到1倍，还可以提高，再增加桶数速度增加不明显，甚至有些倍数还降低了。
前两天在https://bbs.bccn.net/thread-501938-1-1.html参与了桶排序讨论，今天用代码实现了下，并把它合并到我的不同排序算法比较的代码中。
经过反复优化，发现桶排序虽然属于非比较类型排序，却没有什么优势，通过不断调整桶数，观察到当桶数是被排序数的4倍时，才勉强和c qsort的排序速度相当。
当然，我的算法并不是严格意义上的非比较排序，我在二次排序中用了插入排序。现在正考虑设计一个桶数据结构，让该算法可以使二次排序通过递归调用完成，也许能够提高些速度，预计可以达到分治法排序速度，大概是c qsort的1.4倍。
下图是设置不同桶数时排序速度的变化：
下面是我的桶排序代码，欢迎提供宝贵意见：
程序代码：void sort7(double *a, int n)
{//桶排序
const double k = 4; //定义桶和排序总数的比例
double *p, dmax, dmin, s;
int *t, i, j, m, c = (int)(k*n) + 1; //多设置一个桶，防止误差
p = (double *)malloc(n * sizeof(double)); //预备一个空间辅助排序
t = (int*)malloc(c * sizeof(int)); //预备一个空桶
dmax = dmin = a[0];
printf(" 桶数量是待排序数据的%.2f倍\n", k);
for (i = 0; i < n; i++)
{//第一次扫描所有待排序数据，找出其中最大数和最小数，同时将数据转移到预备空间
if (a[i] > dmax)dmax = a[i];
if (a[i] < dmin)dmin = a[i];
p[i] = a[i];
}
s = (dmax - dmin) / (double)(c - 1); //得到每个桶容纳的数据范围基数
if (s == 0)return; //如果基数为0说明待排序数据都相等，无需排序。（double数能否判断等于0，存疑）
for (i = 0; i < c; i++)t[i] = 0; //首先将每个桶归零置空
//第二次扫描所有待排序数组，根据扫描到的数据计算其应该放到哪个桶中，对应桶数据加一。
for (i = 0; i < n; i++)t[(int)((p[i] - dmin) / s)]++;
for (i = j = 0; i < c; i++)
{
if (t[i])
{
j += t[i];
t[i] = j; //确定每个桶的数据上边界位置
if (j < n)a[j] = dmax + 1; //上边界处填入不存在的最大数用于判断插入排序停止位置
}
}
for (i = 0; i < n; i++)
{//第三次扫描所有待排序数据，计算对应桶编号，用桶编号的位置数据作为下标放置待排序数据并执行插入排序
m = (int)((p[i] - dmin) / s);
if (t[m])
{
for (j = --t[m]; j<n-1&&p[i]>a[j + 1]; j++)
a[j] = a[j + 1];
}
a[j] = p[i];
}
free(p);
free(t); //释放本函数申请过的内存
}[此贴子已经被作者于2020-6-15 20:49编辑过]
能编个毛线衣吗？
