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

在运行算法之前,我只需要创建一个桶数组,每组65536个连续值对应一个桶。存储桶将包含其内容的最小值和最大值,但不会存储内容本身。运行该算法后,对桶进行一次遍历。如果有两个连续的非空铲斗,最小(bucket2)-最大(bucket1)<65536,把它们合起来。在算法完成运行之前,不会进行合并。丢弃所有空桶。该算法是线性时间的。

注意到 Bucket Sort .

您不太可能用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;
}

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

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

my @sorted = map { unpack "N" } sort map { pack "N" } @unsorted;

在伪代码中:

while(morenumbers)
  sorted[[unsorted[number]]++
  number++

如果提前知道范围,则可以减少索引值(例如,值-30000以使其进入正确的范围)。