Сохранять порядок ключей (стабильный сортировка) при сортировке с помощью PHP uasort

Ответ 1

Поскольку PHP не поддерживает стабильную сортировку после PHP 4.1.0, вам нужно написать свою собственную функцию.

Это похоже на то, что вы спрашиваете: http://www.php.net/manual/en/function.usort.php#38827

Как говорится в руководстве: "Если два члена сравниваются как равные, их порядок в отсортированном массиве равен undefined". Это означает, что используемый тип не является "стабильным" и может изменять порядок элементов, которые сравниваются с равными.

Иногда вам действительно нужен стабильный вид. Например, если вы сортируете список по одному полю, затем сортируйте его еще раз другим полем, но не хотите потерять порядок из предыдущего поля. В этом случае лучше использовать usort с функцией сравнения, которая учитывает оба поля, но если вы не можете этого сделать, используйте функцию ниже. Это сортировка слиянием, что гарантируется сложностью O (n * log (n)), что означает, что она остается достаточно быстрой, даже если вы используете более крупные списки (в отличие от типа bubblesort и insertion, которые являются O (n ^ 2)).

<?php
function mergesort(&$array, $cmp_function = 'strcmp') {
    // Arrays of size < 2 require no action.
    if (count($array) < 2) return;
    // Split the array in half
    $halfway = count($array) / 2;
    $array1 = array_slice($array, 0, $halfway);
    $array2 = array_slice($array, $halfway);
    // Recurse to sort the two halves
    mergesort($array1, $cmp_function);
    mergesort($array2, $cmp_function);
    // If all of $array1 is <= all of $array2, just append them.
    if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
        $array = array_merge($array1, $array2);
        return;
    }
    // Merge the two sorted arrays into a single sorted array
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
        if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
            $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }
    // Merge the remainder
    while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
    while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
    return;
}
?>

Кроме того, вы можете найти эту тему форума.

Ответ 2

array_multisort пригодится, просто используйте упорядоченный диапазон в качестве второго массива ($order является временным, он служит для заказа эквивалентных элементов первого массив в исходном порядке):

$a = [
  "key-0" => 5,
  "key-99" => 3,
  "key-2" => 3,
  "key-3" => 7
];

$order = range(1,count($a));
array_multisort($a, SORT_ASC, $order, SORT_ASC);

var_dump($a);

Выход

array(4) {
  ["key-99"]=>
  int(3)
  ["key-2"]=>
  int(3)
  ["key-0"]=>
  int(5)
  ["key-3"]=>
  int(7)
}

Я использовал тестовые данные с не-упорядоченными ключами, чтобы продемонстрировать, что он работает правильно. Тем не менее, вот результат вашего теста script:

Array
(
    [key-1] => 10
    [key-4] => 10
    [key-5] => 20
    [key-8] => 20
    [key-6] => 30
    [key-9] => 30
    [key-2] => 40
    [key-0] => 50
    [key-3] => 50
    [key-7] => 50
)

Даунсайд

Он работает только с предопределенными сравнениями, вы не можете использовать свою собственную функцию сравнения. Возможные значения (второй параметр array_multisort()):

Флаги сортировки:

• SORT_ASC - сортировать элементы по возрастанию.
• SORT_DESC - сортировать элементы по убыванию.
• SORT_REGULAR - обычно сравнивайте элементы (не меняйте типы)
• SORT_NUMERIC - сравнить элементы численно
• SORT_STRING - сравнить элементы как строки
• SORT_LOCALE_STRING - сравнить элементы как строки, основанные на текущей локали. Он использует локаль, которую можно изменить, используя setlocale()
• SORT_NATURAL - сравнивайте элементы как строки, используя "естественный порядок", например natsort()
• SORT_FLAG_CASE - можно комбинировать (побитовое ИЛИ) с помощью SORT_STRING или SORT_NATURAL для сортировки строк без учета регистра

Ответ 3

В будущем я поставил набор стабильных вариантов сортировки встроенных функций PHP на Github: https://github.com/vanderlee/PHP-stable-sort-functions, основанный на @Джек и несколько других трюков.

Ответ 4

Для полноты вы также можете проверить преобразование Шварца:

// decorate step
$key = 0;
foreach ($arr as &$item) {
        $item = array($item, $key++); // add array index as secondary sort key
}

// sort step
asort($arr); // sort it

// undecorate step
foreach ($arr as &$item) {
    $item = $item[0]; // remove decoration from previous step
}

Алгоритм сортировки по умолчанию PHP отлично работает с массивами, из-за этого:

array(1, 0) < array(2, 0); // true
array(1, 1) < array(1, 2); // true

Если вы хотите использовать свои собственные критерии сортировки, вы также можете использовать uasort():

// each parameter is an array with two elements
// [0] - the original item
// [1] - the array key
function mysort($a, $b)
{
    if ($a[0] != $b[0]) {
        return $a[0] < $b[0] ? -1 : 1;
    } else {
        // $a[0] == $b[0], sort on key
        return $a[1] < $b[1] ? -1 : 1; // ASC
    }
}

Ответ 5

Это решение, с помощью которого вы можете добиться стабильного сортировки в функции usort

public function sortBy(array &$array, $value_compare_func)
{
    $index = 0;
    foreach ($array as &$item) {
        $item = array($index++, $item);
    }
    $result = usort($array, function($a, $b) use ($value_compare_func) {
        $result = call_user_func($value_compare_func, $a[1], $b[1]);
        return $result == 0 ? $a[0] - $b[0] : $result;
    });
    foreach ($array as &$item) {
        $item = $item[1];
    }
    return $result;
}

Ответ 6

Просто для того, чтобы выполнить ответы с некоторым конкретным случаем. Если ключи массива $array являются стандартными, то достаточно простого array_values(asort($array)) (здесь, например, в порядке возрастания)