Подсчет сортировки в PHP

Question

В проекте PHP у меня есть некоторые данные, которые я хочу отсортировать с использованием линейного времени, простой сортировки:

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v)
    $count[$v]++;
$sorted = array();    
foreach ($count as $v => $c)
    for ($i = 0; $i < $c; $i++)
        $sorted[] = $v;

Проблема в том, что вышеприведенное очевидно не работает.Массив php больше похож на хэш-карту, чем на массив.Код можно заставить работать, вставив ksort($count) перед последним циклом, но ksort запускается в O(nlogn), который уничтожает всю точку.

Есть ли способ выполнить линейную сортировку по времени в php?Возможно, использовать какой-то параметр для array() или какую-то совершенно другую структуру?

Answer 1

Вы не правильно следовали алгоритму . Это O (n).

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v) {
    $count[$v] = isset($count[$v]) ? $count[$v] + 1 : 1;
}
$sorted = array();
$min = min($ar);
$max = max($ar);
for ($i=$min; $i<=$max; $i++) {
    if (isset($count[$i])) {
        for ($j=0; $j<$count[$i]; $j++) {
            $sorted[] = $i;
        }
    }
}

также см. array_count_values ​​ () или альтернативно вычислите минимальное и максимальное значения в цикле подсчета.

Answer 2

Утвержденный ответ неверен.Правильно:

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v) {
    $count[$v] = isset($count[$v]) ? $count[$v] + 1 : 1;
}
$sorted = array();
$min = min($ar);
$max = max($ar);
for ($i=$min; $i  <=   $max; $i++) {
    if (isset($count[$i])) {
        for ($j=0; $j<$count[$i]; $j++) {
            $sorted[] = $i;
        }
    }
}

Answer 3

Чтобы отсортировать $ar в своей собственной переменной ($sorted), это довольно тривиально:

$sorted = $ar;
sort($sorted);

Что заставляет меня думать, что ваш вопрос и комментарий не дают полной картины.

Редактировать: Теперь, после того, как вы пояснили, что хотите реализовать конкретный алгоритм (и у вас уже есть ответ, который показывает некоторые моменты, которые сначала неправильно его реализовали), я думаю, стоит сосредоточиться по другому аспекту вашего вопроса:

Вы сравниваете сложность двух (теоретических) алгоритмов, но оставляете в стороне, как реализованы алгоритмы.

PHP sort() - даже основываясь на «плохом» быстрой сортировке , превзойдет вашу собственную реализацию PHP-кода другого алгоритма по номерам .

Вы только что сравнили неправильные параметры здесь. Сложность функции не говорит о многом, когда вы сравниваете встроенную функцию PHP с некоторой функцией в вашем пользовательском коде.

Answer 4

Добавление некоторых комментариев к коду, чтобы показать вам, почему это не делает то, что, как вы думаете, должно делать.

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);

$count = array();
foreach ($ar as $v) {
    // add each number in $ar to $count.
    // the first number in $ar is 7, so 7 will be the first number in $count.
    // because 7 is in $ar 3 times, $count[7] == 3.
    $count[$v]++;
}

// the output of print_r will be very revealing:
print_r($count);
/*Array
(
    [7] => 3
    [2] => 1
    [0] => 2
    [3] => 1
    [8] => 1
    [12] => 1
    [6] => 1
)*/

$sorted = array();    
foreach ($count as $v => $c) {
    // the first entry: $count[7] == 3
    // so add 7 to $sorted 3 times.
    // the second entry: $count[2] == 1
    // so add 2 to $sorted 1 time.
    // etc.
    for ($i = 0; $i < $c; $i++) {
        $sorted[] = $v;
    }
}

Это просто группирует числа на основе их расположения в первом массиве.

Answer 5

Если я правильно понимаю ваш вопрос и комментарий, просто с помощью сортировки ($ count) сработает нет?

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$sorted = $ar;
sort($sorted);
var_dump($ar);
var_dump($sorted);

Результат:

array(7,2,0,3,8,0,12,7,6,7);
array(0,0,2,3,6,7,7,7,8,12);

Но мне интересно, что такое foreach ($ ar as $ v) $ count [$ v] ++; действительно ... не имеет смысла ...