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

Question

Этот вопрос на самом деле вдохновлен другим здесь, на SO, и я хотел немного его расширить.

Имея ассоциативный массив в PHP, можно ли сортировать его значения, но где значения равны, чтобы сохранить исходный порядок ключей, используя один (или более) из встроенной в PHP функции сортировки?

Вот скрипт, который я использовал для тестирования возможных решений (не нашел):

<?php
header('Content-type: text/plain');
for($i=0;$i<10;$i++){
    $arr['key-'.$i] = rand(1,5)*10;
}
uasort($arr, function($a, $b){
    // sort condition may go here //
    // Tried: return ($a == $b)?1:($a - $b); //
    // Tried: return $a >= $b; //
});
print_r($arr);
?>

Подводный камень : поскольку ключи упорядочены в исходном массиве, не пытайтесь предложить какую-либо сортировку по ключу, чтобы восстановить исходный порядок. Я сделал с ними пример, чтобы было проще визуально проверить их порядок в выводе.

Answer 1

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

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

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

Иногда вам действительно нужна стабильная сортировка. Например, если вы сортируете список по одному полю, затем сортируете его снова по другому полю, но не хотите терять порядок из предыдущего поля. В этом случае лучше использовать usort с функцией сравнения, которая учитывает оба поля, но если вы не можете этого сделать, используйте функцию ниже. Это сортировка слиянием, гарантирующая сложность O (n * log (n)), что означает, что она остается достаточно быстрой даже при использовании больших списков (в отличие от сортировки пузырьков и сортировки вставками, которые 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;
}
?>

---

Также вы можете найти эту ветку форума интересной.

Answer 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)
}

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

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 для сортировки строк без учета регистра

Answer 3

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

Answer 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
    }
}

Answer 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;
}

Answer 6

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