Нежелательное поведение PHP usort

Question

У меня проблема с PHP usort().Предположим, у меня есть такой массив (это упрощение, я не работаю с именами, у меня есть массив объектов, а не массивов):

$data = array(
    array('name' => 'Albert',      'last' => 'Einstein'),
    array('name' => 'Lieserl',     'last' => 'Einstein'),
    array('name' => 'Alan',        'last' => 'Turing'  ),
    array('name' => 'Mileva',      'last' => 'Einstein'),
    array('name' => 'Hans Albert', 'last' => 'Einstein')
);

Как видите, массивсортируется произвольно.

Теперь, если хотите отсортировать по last, я делаю:

function sort_some_people($a, $b) { return strcmp($a['last'], $b['last']); }
usort($data, 'sort_some_people');

И у меня есть:

Array (
    [0] => Array ( [name] => Mileva       [last] => Einstein )
    [3] => Array ( [name] => Albert       [last] => Einstein )
    [1] => Array ( [name] => Lieserl      [last] => Einstein )
    [2] => Array ( [name] => Hans Albert  [last] => Einstein )
    [4] => Array ( [name] => Alan         [last] => Turing   )
)

Это нормально, теперь они отсортированы по last.Но, как видите, я только что полностью потерял предыдущую сортировку.Что я говорю?Я хочу сохранить сортировку массива, как это было раньше, но в качестве вторичной сортировки.Надеюсь, мне было ясно. Практически Я хочу отсортировать данные, используя что-то вроде usort() (то есть полностью настраиваемая сортировка), но если поле сортировки между двумя элементами одинаково, я хочу сохранить их относительное положение как было раньше.Учитывая приведенный пример, я хочу, чтобы Lieserl Einstein появлялся до Mileva Einstein, потому что это было так в начале.

Answer 1

Алгоритмы сортировки, используемые в PHP, имеют это свойство, где порядок не определен, если элементы совпадают.

Если вам нужно сохранить заказ, то вам нужно свернуть свой код.

К счастью, кто-то уже имеет: http://www.php.net/manual/en/function.usort.php#38827

$data = array(
    array('name' => 'Albert',      'last' => 'Einstein'),
    array('name' => 'Lieserl',     'last' => 'Einstein'),
    array('name' => 'Alan',        'last' => 'Turing'  ),
    array('name' => 'Mileva',      'last' => 'Einstein'),
    array('name' => 'Hans Albert', 'last' => 'Einstein')
);

function sort_some_people($a, $b) {
        return strcmp($a['last'], $b['last']);
}

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

mergesort($data, 'sort_some_people');

print_r($data);

Выход:

Array
(
    [0] => Array
        (
            [name] => Albert
            [last] => Einstein
        )

    [1] => Array
        (
            [name] => Lieserl
            [last] => Einstein
        )

    [2] => Array
        (
            [name] => Mileva
            [last] => Einstein
        )

    [3] => Array
        (
            [name] => Hans Albert
            [last] => Einstein
        )

    [4] => Array
        (
            [name] => Alan
            [last] => Turing
        )

)

Вуаля!

Answer 2

Вы запрашиваете стабильный алгоритм сортировки , который не предлагает php.Имейте в виду, что даже если иногда это может показаться стабильным, это не гарантируется, и, следовательно, вероятность неправильного поведения при определенных входных данных.

Если вы знаете критерии сортировки других столбцов, вы можете прибегнуть ко всем сразуполучить желаемое поведение. array_multisort делает это.Ниже приведен более мощный способ, заключающийся в том, что логика сравнения полностью определяется пользователем.

// should behave similar to sql "order by last, first"
$comparatorSequence = array(
    function($a, $b) {
        return strcmp($a['last'], $b['last']);
    }
  , function($a, $b) {
        return strcmp($a['first'], $b['first']);
    }
  // more functions as needed
);

usort($theArray, function($a, $b) use ($comparatorSequence) {
    foreach ($comparatorSequence as $cmpFn) {
        $diff = call_user_func($cmpFn, $a, $b);
        if ($diff !== 0) {
            return $diff;
        }
    }
    return 0;
});

Если вам действительно нужна стабильная сортировка, поскольку существующий порядок элементов не определен правильно, попробуйте написать собственную сортировку.Например, пузырьковая сортировка очень легко написать.Это хорошее решение, если количество элементов в ваших списках относительно мало, в противном случае обратите внимание на реализацию одного из других алгоритмов стабильной сортировки.

Answer 3

$compare = strcmp($a['last'], $b['last']);
if ($compare == 0)
    $compare = strcmp($a['name'], $b['name']);
return $compare

Answer 4

Попробуйте это:

function sort_some_people($a, $b)
{
    $compareValue = 10 * strcmp($a['last'], $b['last']);
    $compareValue += 1 * strcmp($a['name'], $b['name']);
    return $compareValue;
}

Образец: http://codepad.org/zkHviVBM

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