Как отсортировать огромный массив элементов по определенному порядку, определенному массивом?

Question

Мне нужно реализовать какой-то специфический алгоритм сортировки.У меня есть два массива:

$items = array(
  array("id" => "…", "type" => "alpha"),
  array("id" => "…", "type" => "beta"),
  array("id" => "…", "type" => "company"),
  array("id" => "…", "type" => "marketing"),
  array("id" => "…", "type" => "beta"),
  array("id" => "…", "type" => "company"),
  array("id" => "…", "type" => "alpha"),
  array("id" => "…", "type" => "alpha"),
  array("id" => "…", "type" => "company"),
  array("id" => "…", "type" => "marketing"),
  […]
);

$order = array("company", "marketing", "alpha", "beta" );

Как вы, вероятно, можете себе представить, мне нужно отсортировать $items в порядке, указанном в $order.

Answer 1

Пройдите через $items и внесите все в словарь, используя в качестве ключа «тип».Затем выполните $order, найдите список элементов, соответствующих этому «типу», и добавьте их в отсортированный список.Работает в O(n+k), k = |order|.

Answer 2

Вы можете сортировать с помощью пользовательской функции сравнения, используя usort

usort($items, "cmp");

function cmp($a, $b)
{
  $order = array("company" => 0, "marketing" => 1, "alpha" => 2, "beta" => 3);

  $order_a = $order[$a["type"]];
  $order_b = $order[$b["type"]];

  if ($order_a == $order_b) {
    return 0;
  }
  return ($order_a < $order_b) ? -1 : 1;
}

Answer 3

Очень похоже на Озгур !! Тем не менее, я бы встроил функциональность для обработки неожиданных значений, которые не учитываются в порядке. Они помещаются в конец отсортированного массива.

<code>usort($items,"compare");
echo "<pre>";
print_r($items);
echo "

"; функция сравнения ($ a, $ b) { $ order = array ("company" => 1, "marketing" => 2, "alpha" => 3, "beta" => 4); $ ax = $ order [$ a ['type']]; $ bx = $ order [$ b ['type']]; if ($ ax <1) вернет 1; if ($ ax == $ bx) return 0; возврат ($ ax> $ bx)? 1: -1; }

Answer 4

Вы можете сделать наивную реализацию функции сортировки пользователя:

function mySort($a, $b) {
    global $order;

    return array_search($a['type'], $order) - array_search($b['type'], $order);
}

А затем сделайте usort():

usort($items, 'mySort');

Возможно, не очень эффективно, но оно работает .

---

UPDATE
Чтобы избежать многочисленных вызовов array_search(), вы можете перевернуть массив $order один раз. Это заменит array_search() простым поиском:

$reversed_order = array_flip($order);

function mySort($a, $b) {
    global $reversed_order;

    return $reversed_order[$a['type']] - $reversed_order[$b['type']];
}

Должно быть более эффективным. ( демо )

Answer 5

используйте usort, который является эффективным алгоритмом PHP и может работать в зависимости от предоставленных вами условий.

http://php.net/manual/en/function.usort.php

Вот бегущий код, вы можете сравнить его с вашими данными: http://codepad.org/MRpZQkKk

Это даст вам больше контроля, если вы захотите изменить критерии сортировки, также сложность довольно быстрая, она должна быть O (n log n) (внутренняя сортировка), и сложность пространства также низкая.

Вот больше об этом: Какие алгоритмы сортировки применяется в usort?

  <?php

    $items = array(
      array("id" => "…", "type" => "alpha"),
      array("id" => "…", "type" => "beta"),
      array("id" => "…", "type" => "company"),
      array("id" => "…", "type" => "marketing"),
      array("id" => "…", "type" => "beta"),
      array("id" => "…", "type" => "company"),
      array("id" => "…", "type" => "alpha"),
      array("id" => "…", "type" => "alpha"),
      array("id" => "…", "type" => "company"),
      array("id" => "…", "type" => "marketing"),

    );

    $order = array("company", "marketing", "alpha", "beta" );

    $orderIndexes = array(); /* cache indexes of the order keys */
    for($i = 0 ; $i < count($order) ; $i++ )
    {
       $orderIndexes[$order[$i]] = $i ;
    }


    /* we have something like :
    $orderIndexes = array('company' => 0 , 'marketing' => 1 , ....);
    */



    function myCriteria($item1,$item2)   /* this is the function used to decide order */
    {  global $orderIndexes;
       $index1 = $orderIndexes[$item1['type']];
       $index2 = $orderIndexes[$item2['type']];

       return $index1 - $index2 ;    // negative means $item1 precedes $item2

    }

usort($items,"myCriteria");
print_r($items);

?>