Что такое быстрый алгоритм сортировки для целых чисел 0-65535?

Question

Мне нужно отсортировать несколько целых чисел, которые могут иметь значения от 30.000.000 до 350.000.000. Будут от 0 до 65.535 целых чисел, при этом средний счет равен 20 000. Использование ОЗУ не имеет значения, и важна только скорость.

Позже я также должен разбить их на группы, причем делитель всегда устанавливается, когда разрыв между двумя из этих значений составляет> 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; 

Answer 1

Я бы просто сделать массив из ведра перед запуском алгоритма, по одному для каждой группы 65536 последовательных значений. Ведра будут содержать минимальное и максимальное значение их содержимого, но не будут хранить содержимое сами. После запуска алгоритма выполните один проход над ведрами. Если есть два последовательных непустых ведра с min (bucket2) -max (bucket1) < 65536, объедините их. Комбинация не произойдет, пока алгоритм не завершится. Отбросьте любые пустые ведра. Этот алгоритм является линейным временем.

Обратите внимание: Bucket Sort.

Answer 2

Я хотел бы использовать базисное рода, так как вам нужно сгруппировать выход.

Answer 3

Я просто хочу сказать, базисный вид, http://en.wikipedia.org/wiki/Radix_sort однако, что может быть немного выше, что вы хотите реализовать, Introsort, как правило, принимается сортировка решения для данных http://en.wikipedia.org/wiki/Introsort, это изменение сортировки, который переключается на пирамидальную сортировку, когда его достигает меньших наборов, поскольку он быстрее на небольших наборах, чем quicksort.

Answer 4

Если вы используете число в качестве индекса для массива и затем увеличиваете счетчик этой позиции, вы «сгруппировали» их и выполнили за один проход.

в псевдокоде:

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

Если диапазон известен заранее, вы можете уменьшить индекс значения (например, значение-30000, чтобы привести его в нужном диапазоне).

Answer 5

Это маловероятно, что вы будете иметь возможность написать алгоритм сортировки в Perl, который будет работать лучше, чем встроена sort функции в Perl:

Вы можете экспериментировать с сортировкой прагмой, чтобы увидеть, если конкретный алгоритм лучше:

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 6

Я хотел бы попробовать это:

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