我必须对一些整数进行排序,这些整数的值介于 30.000.000 和 350.000.000 之间。将有 0 到 65.535 个整数,平均数为 20.000。 RAM 使用无关紧要,速度很重要。
稍后我还必须将它们分成几组,只要其中两个值之间的差距大于 65.535,就会始终设置分界线,这正是我需要算法的原因。
如果有任何不同,该算法将在 Perl 脚本中使用。
编辑:经过深思熟虑并阅读了答案后,我开始意识到一件事:我实际上并不关心数据本身。因为我真的只想找到具有小间隙的组的开始和结束值,所以排序只需要创建桶并且可以丢弃数据。
Edit2:经过一些测试和尝试提供的答案后,我发现最快的方法是:
my @sort = sort {$a <=> $b} @item_offsets;
my @buckets;
my $start = shift @sort;
push @buckets, [$start,$start];
for my $item ( @sort ) {
if ( $item < $buckets[$#buckets][1]+$gap ) {
$buckets[$#buckets][1] = $item;
}
else {
push @buckets, [$item,$item];
}
}
say $#buckets;
最佳答案
我只是在运行算法之前制作了一个桶数组,每组一个桶对应 65536 个连续值。桶将包含其内容的最小值和最大值,但不会存储内容本身。运行算法后,对桶进行单次传递。如果有两个连续的非空桶且 min(bucket2)-max(bucket1) < 65536,则合并它们。在算法完成运行之前不会发生合并。丢弃任何空桶。该算法是线性时间的。
注意Bucket Sort .
关于perl - 0-65535 整数最快的排序算法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/285005/