Алгоритм сортировки Radix PHP — преобразование типов в порядке?

Question

Алгоритм сортировки Radix PHP — преобразование типов в порядке?

Это функция, которую я написал для сортировки по Radix в PHP.
Это работает для всех случаев, когда массив заполнен числами больше 0.

function radix_sort($arr) {

// Find the number of passes needed to complete the sort
$passes = strlen((string)max($arr));
$buckets = [];

// Start the passes
for($i = 1; $i <= $passes; $i++) {
// Create - reinitialize some buckets
for ($b = 0; $b <= 9; $b++) {
$buckets[$b] = [];
}

for ($j = 0; $j < count($arr); $j++) {
// Drop into the proper bucket based on the significant digit
$numStr = (string)$arr[$j];
if (strlen($numStr) < $i) {
$bucketsIndex = 0;
} else {
$bucketsIndex = $numStr[strlen($numStr) - $i];
}
array_push($buckets[$bucketsIndex], $arr[$j]);
}

// Repopulate our array by pulling out of our buckets
$k = 0;
foreach ($buckets as $bucket) {
foreach ($bucket as $value) {
$arr[$k] = $value;
$k++;
}
}
}
return $arr;
}

Я чувствую, что происходит слишком много преобразования типов. Это нормально делать это? Если бы я хотел извлечь N-ую цифру из большого числа, есть ли лучший способ в PHP?

0

algorithm php radix-sort sorting

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы можете конвертировать все значения в string до функции, а затем вернуться к int в конце:

function radix_sort($arr) {

$arr = array_map ('strval', $arr) ;
$passes = strlen(max($arr)) ; // Should still work since all values are numeric

/* Do your stuff... */

return array_map ('intval', $arr) ;
}

Тогда в вашем внутреннем цикле вы можете сохранить длину (я не знаю, сложность strlen в PHP, но я предположил, что это не так O(1)):

for ($j = 0; $j < count($arr); $j++) {
// Drop into the proper bucket based on the significant digit
$numStr = $arr[$j];
$numLen = strlen($numStr) ;
if ($numLen < $i) {
$bucketsIndex = 0;
} else {
$bucketsIndex = $numStr[$numLen - $i];
}
array_push($buckets[$bucketsIndex], $arr[$j]);
}

Или вы можете даже (если у вас достаточно памяти) использовать массив для предварительного вычисления длины:

$lengths = array_map ('strlen', $arr) ;

0