Параметры функции обратного вызова USORT в PHP

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

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

Если вы не знакомы, вы можете посмотреть, как простой наивный алгоритм, такой как bubblesort, будет использовать функция сравнения.

За кулисами PHP использует быструю сортировку.

Точное определение $a и $b будет зависеть от алгоритма, используемого для сортировки массива. Чтобы отсортировать что-либо, у вас должно быть средство для сравнения двух элементов, для чего используется функция обратного вызова. Некоторые алгоритмы сортировки могут запускаться в любом месте массива, другие могут запускаться только в определенной его части, поэтому в $a и $b нет фиксированного значения, за исключением того, что это два элемента в массиве, которые должны сравнивать по действующему алгоритму.

Этот метод можно использовать, чтобы пролить свет на то, какой алгоритм использует PHP.

<?php

$myArray = array(1, 19, 18, 12, 56);

function compare($a, $b) {
    echo "Comparing $a to $b\n";
    if ($a == $b) return 0;
    return ($a < $b) ? -1 : 1;
}

usort($myArray,"compare");
print_r($myArray);
?>

Выход

vinko@mithril:~$ php sort.php
Comparing 18 to 19
Comparing 56 to 18
Comparing 12 to 18
Comparing 1 to 18
Comparing 12 to 1
Comparing 56 to 19
Array
(
    [0] => 1
    [1] => 12
    [2] => 18
    [3] => 19
    [4] => 56
)

Из вывода и просмотра источника мы видим, что используемая сортировка действительно является реализацией quicksort, проверьте для Zend/zend_qsort.c в исходном коде PHP (версия, на которую ссылаются, устарела, но не сильно изменилась).

Он выбирает опорную точку в середине массива, в данном случае 18, затем ему необходимо переупорядочить список так, чтобы все элементы, которые меньше (согласно используемой функции сравнения), чем опорная точка, располагались перед опорной точкой, и чтобы все элементы, большие, чем точка опоры, идут после него, мы можем видеть, как это происходит, когда он сначала сравнивает все с 18.

Некоторые дальнейшие схематические пояснения.

Step 0: (1,19,18,12,56); //Pivot: 18, 
Step 1: (1,12,18,19,56); //After the first reordering
Step 2a: (1,12);         //Recursively do the same with the lesser, here 
                         //pivot's 12, and that's what it compares next if 
                         //you check the output.
Step 2b: (19,56);        //and do the same with the greater

usort() или uasort() имеют ошибку человеческого восприятия при отсортированном результате. См. сегмент кода:

function xxx($a,$b) { if ($a==$b) return 0; else return $a<$b?-1:1; }
$x=array(1=>10,2=>9,3=>9,4=>9,5=>6,6=>38);
uasort($x,'xxx');
print_r($x);

результат:

Array ( [5] => 6 [4] => 9 [3] => 9 [2] => 9 [1] => 10 [6] => 38 )

Вы видите ошибку? Нет? Хорошо, позвольте мне объяснить это. Исходные три элемента «9» расположены в ключевом порядке: 2,3,4. Но в результате три элемента '9' теперь находятся в ключевом порядке: 4,3,2, т.е. элементы с одинаковым значением находятся в обратном ключевом порядке после сортировки.

Если элемент имеет только одно значение, как в приведенном выше примере, для нас это нормально. Однако, если элемент является составным значением, это может вызвать ошибку человеческого восприятия. См. другие сегменты кода. Нам нужно отсортировать множество точек по горизонтали, т.е. отсортировать их по возрастанию значения x-координаты:

function xxx($a,$b) { if ($a['x']==$b['x']) return 0; else return $a['x']<$b['x']?-1:1; }
$x=array(1=>array('x'=>1, 'v'=>'l'),2=>array('x'=>9, 'v'=>'love'),
       3=>array('x'=>9,  'v'=>'Lara'),4=>array('x'=>9,  'v'=>'Croft'),
       5=>array('x'=>15,  'v'=>'and'),6=>array('x'=>38,  'v'=>'Tombraider'));
uasort($x,'xxx');
print_r($x);

результат:

Array ( [1] => Array ( [x] => 1 [v] => l ) [4] => Array ( [x] => 9 [v] => croft ) 
             [3] => Array ( [x] => 9 [v] => Lara ) [2] => Array ( [x] => 9 [v] => love )
             [5] => Array ( [x] => 15 [v] => and ) [6] => Array ( [x] => 38 [v] => Tombraider ) )

Вы видите, что «Я люблю Лару Крофт и Tombraider» становится «Я люблю Крофт, Лару и Tombraider».

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