Radix Сортировать в JavaScript
-
26-09-2019 - |
Вопрос
Я придумал следующее, но это предсказуемо не работает.
var t = new Array(a.length);
var r = 4;
var b = 64;
var count = new Array(1<<r);
var pref = new Array(1<<r);
var groups = Math.ceil(b / r);
var mask = (1 << r) - 1;
var shift = 0;
for(var c = 0; c < groups; c++)
{
shift += r;
for(var j = 0; j < count.length; j++)
{
count[j] = 0;
}
for(var i = 0; i < a.length; i++)
{
count[ (a[i] >> shift) & mask ]++;
}
pref[0] = 0;
for(var i = 0; i < count.length; i++)
{
pref[i] = pref[i-1] + count[i-1];
}
for(var i = 0; i < a.length; i++)
{
t[ pref[ (a[i] >> shift) & mask ]++ ] = a[i];
}
for(var i = 0; i < a.length; i++)
{
a[i] = t[i];
}
// a is sorted?
}
Решение
Этот цикл делает в основном то же самое, в другом состоянии JavaScript-Y:
for (var div = 1, radix = 16; div < 65536 * 65536; div *= radix) {
var piles = [];
for (var i = 0; i < a.length; ++i) {
var p = Math.floor(a[i] / div) % radix;
(piles[p] || (piles[p] = [])).push(a[i]);
}
for (var i = 0, ai = 0; i < piles.length; ++i) {
if (!piles[i]) continue;
for (var pi = 0; pi < piles[i].length; ++pi)
a[ai++] = piles[i][pi];
}
}
Вместо того, чтобы сделать это как программист C, этот цикл создает список списков, один список для каждого возможного 4-битного значения. Я избегаю операторов Bit-Shift, потому что это JavaScript, и пока они делают работай, Вещи становятся смешными, когда цифры получают большие.
Начиная с низких 4 битов каждого значения в «A», код копирует этот элемент «A» до конца одного из «сваи», которые являются тем, что соответствует 4-битному значению. Затем он собирает груды и восстановит «a», начиная со всех ценностей, низкие 4 бита которых было 0, то 1 и т. Д. (Очевидно, что будут некоторые пробелы, поэтому те, которые пропущены.) В конце каждой итерации Общей цикле Divisor умножается на Radix, так что следующий набор из 4 битов будет рассмотрен.
Как только дивизор исчерпал доступный диапазон целых чисел, это сделано.
Обратите внимание, что это будет работать только для положительный числа. Делать это с отрицательными числами становится немного странным; Возможно, будет легче раскрыть отрицательные числа в отдельный массив, переверните знак, сортируйте, затем обратный. Сортируйте положительные числа, а затем, наконец, приклеивают обратные отрицательные числа (снова переворачивая знаки) перед передней частью отсортированных положительных чисел.
Другие советы
это
for(var i = 0; i < count.length; i++)
{
pref[i] = pref[i-1] + count[i-1];
}
это проблема, потому что на первой итерации, i
равен нулю pref[ 0 - 1 ]
не собирается работать очень хорошо.
У меня нет ссылки на Radix сортирует удобные, чтобы определить, что вы должны делать здесь.