桶排序算是一个相对较快的排序,我们可以理解为是计数排序的升级版,桶排序从 1956 年就开始被使用,该算法的基本思想是由 E.J.Issac R.C.Singleton 提出来。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这几点:
1、在额外空间充足的情况下,尽量增大桶的数量
2、使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
3、对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
4、当输入的数据可以均匀的分配到每一个桶中,排序最快
5、当输入的数据被分配到了同一个桶中最慢!
桶排序示意图
元素分布在桶中:
然后,元素在每个桶中排序:
易语言桶排序源码
.版本 2 .子程序 桶排序, , 公开, 排序正整数 注意: 最小不能为0,也不能为负数 // 真为从小到大,反之假 .参数 参数_原始, 整数型, 参考 数组 .参数 参数_顺序, 逻辑型, 可空 .局部变量 m, 整数型 .局部变量 n, 整数型, , "0" .局部变量 a, 整数型 .局部变量 b, 整数型 .计次循环首 (取数组成员数 (参数_原始), a) ' .如果真 (m < 参数_原始 [a]) m = 参数_原始 [a] .如果真结束 .计次循环尾 () 重定义数组 (n, 假, m) ' .计次循环首 (取数组成员数 (参数_原始), a) n [参数_原始 [a]] = n [参数_原始 [a]] + 1 .计次循环尾 () .如果真 (是否为空 (参数_顺序) = 真) 参数_顺序 = 真 .如果真结束 .如果 (参数_顺序 = 真) .计次循环首 (取数组成员数 (n), a) .计次循环首 (n [a], ) b = b + 1 参数_原始 [b] = a .计次循环尾 () .计次循环尾 () .否则 b = 取数组成员数 (参数_原始) .计次循环首 (取数组成员数 (n), a) .计次循环首 (n [a], ) 参数_原始 [b] = a ' b = b - 1 .计次循环尾 () .计次循环尾 () .如果结束