0-65535整数的最快排序算法是什么？

Question

我必须对一些整数进行排序,这些整数的值可以在30.000.000到350.000.000之间.整数将在0到65.535之间,平均计数为20.000.RAM的使用是无关紧要的,速度只是重要的.

稍后,我还必须将它们分成组,只要这些值中的两个之间的差距> 65.535,就必须设置除法,这就是我需要的算法.

如果它有任何区别,该算法将用于Perl脚本.

编辑:经过思考并阅读答案后我才意识到:我实际上并不关心数据本身.因为我真的只想找到具有小间隙的组的起始值和结束值,所以排序只需要创建存储桶并且可以丢弃数据.

编辑2:经过一些测试并尝试提供答案后,我发现的最快方式是:

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;

Answer 1

你不太可能在Perl中编写一个比Perl的内置sort函数更好的排序算法:

@numbers = sort {$a <=> $b} @numbers;

您可以尝试使用sort pragma来查看特定算法是否更好:

use sort '_quicksort';
use sort '_mergesort';

由于您的切割点会根据数据分布而有所不同,我认为您需要先对整个列表进行排序,然后循环切割它以进行切割.

my $prev  = shift @numbers;  # already sorted
my @group = [$prev];
my $i     = 0;

foreach my $n (@numbers) {
    $i++ if ($n - $prev > 65535);
    push @{$group[$i]}, $n;
    $prev = $n;
}

Answer 2

我在运行算法之前只生成一个桶数组,每组包含65536个连续值.存储桶将包含其内容的最小值和最大值,但不会存储内容本身.运行算法后,对存储桶执行一次传递.如果有两个连续的非空桶,其中min(bucket2)-max(bucket1)<65536,则将它们组合起来.在算法完成运行之前不会发生组合.丢弃任何空桶.该算法是线性时间.

注意Bucket Sort.

Answer 3

我使用基数排序,因为您需要对输出进行分组.

Answer 4

我只是想说radix sort,http://en.wikipedia.org/wiki/Radix_sort然而这可能比你想要实现的要高一些,Introsort通常是公认的数据排序解决方案http:// en .wikipedia.org/wiki/Introsort,它是quicksort的一种变体,当它到达较小的集合时切换到heapsort,因为它在较小的集合上比quicksort更快.