用 usort() 排序这个数组的机制是什么？

Question

<?php
function list_cmp($a, $b) {
    global $order;

    foreach ($order as $key => $value) {
        if ($a == $value) {
            return 0;
        }

        if ($b == $value) {
            return 1;
        }
    }
}

$order[0] = 1;
$order[1] = 3;
$order[2] = 4;
$order[3] = 2;

$array[0] = 2;
$array[1] = 1;
$array[2] = 3;
$array[3] = 4;
$array[4] = 2;
$array[5] = 1;
$array[6] = 2;

usort($array, "list_cmp");

我知道这是插入排序（不是快速排序，因为数组有 6-15 个元素）。我看到 $a-$b 对与顺序进行了比较，如果 list_cmp 回调函数 returns 1，则当前 $b 值移向数组的开头。这就是 usort() 的工作原理，只有 $b 被移动。我假设它总是朝这个方向，而且这个假设是正确的。

$a-$b 对是这样的 - 2-1, 2-3, 1-3, 2-4, 3-4, 2-2, 2-1, 2-1, 4- 1、3-1、1-1、2-2，这些是在所有步骤中返回的值 - 1,1,0,1,0,0,1,1,1,1,0,0 （如果返回 1，则 $b 被移动，如果返回 0，我猜 usort() 正在寻找正确的插入点，但这是如何工作的？我没有看到它是如何工作的，它的机制是什么或在哪里？)

我知道它是 1) 比较 2) 找到插入点和 3) 插入，它看起来像这样：

-- [2,1],3,4,2,1,2 -> 1./2./3. compare [2,1], find and insert 1 before 2
-- 1,[2,3],4,2,1,2 -> 1./2. compare [2,3], find insert point for 3 (since order of 3 < order of 2)
-- [1,3],2,4,2,1,2 -> 3. compare [1,3], found insert point for 3 before 2
-- 1,3,[2,4],2,1,2 -> 1./2. compare [2,4], find insert point for 4 (since order of 4 < order of 2) 
-- 1,[3,4],2,2,1,2 -> 3. compare [3,4], found insert point for 4 before 2
-- 1,3,4,[2,2],1,2 -> 1. compare [2,2], skip
-- 1,3,4,2,[2,1],2 -> 1./2. compare [2,1], find insert point for 1
-- 1,3,4,[2,1],2,2 -> 2. compare [2,1], find insert point for 1
-- 1,3,[4,1],2,2,2 -> 2. compare [4,1], find insert point for 1
-- 1,[3,1],4,2,2,2 -> 2. compare [3,1], find insert point for 1
-- [1,1],3,4,2,2,2 -> 3. compare [1,1], fond insert point for 1 before 3
-- 1,1,3,4,2,[2,2] -> 1. compare [2,2], skip
-- sorted: 1,1,3,4,2,2,2

但同样，我基本上没有看到找到插入点的机制。这个的动态是 - list_cmp returns 1 - 移动 $b （并向数组的开头），但是找到正确位置的机制是什么？可以说，这是在 usort() 中，但我们不会在 1,2,3,4,x,6,7,8,9 处生成类似 putting 5 的东西。结果是 1,1,3,4,2,2,2，这是基于 $order 数组中的内容。

Answer 1

首先，您自定义的比较函数不正确。当 $a 必须位于排序数组中的 $b 之前时，它必须 return 为负值，当 $a 和 [=11= 时，它必须为零 (0) ] 相等且为正值，当 $a 必须位于排序数组中的 $b 之后。

如果你读 "$a 小于 $b" 而不是 "$a 停留在 [= 之前11=]"（和 "greater" 而不是 "after"）你得到数组升序排序.但是没有人说数组必须升序排序，也没有自定义数组排序函数进行降序排序。最终数组中元素的顺序由提供的自定义比较函数决定。

你说的是问题中的"insertion points"。有几十种排序算法。其中一些从一个空列表开始并将元素插入到它们的最终位置，另一些交换两个项目并就地进行排序。

我不知道u*sort() PHP functions (and for the daily use I don't even care) but I assume it uses quicksort或其他快速算法实现的是什么算法。出于好奇，快速排序不会插入任何内容，它会交换项目。

不管用什么算法，排序主要用到的操作是两个item的比较。算法在发现哪个项目应该留在另一个项目之前如何使用这些项目是另一回事，但它不会干扰比较本身。

Answer 2

http://php.net/manual/en/function.usort.php 状态：

value_compare_func The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second

当您调用该函数时，它会采用任意两个值并确定它们的顺序是否正确。

实际上它所做的只是将 $b 变量相对于 $a.

在数组中向上或向下移动

向您的函数添加一些输出可以告诉您发生了什么：

<?php
function list_cmp($a, $b) {
    global $order;

    echo "comparing $a and $b...\n";
    foreach ($order as $key => $value) {
        echo "  checking against $value\n";
        if ($a == $value) {
            echo "    $a ($a) == $value: returning 0\n";
            return 0;
        }

        if ($b == $value) {
            echo "    $b  ($b) == $value: returning 1\n";
            return 1;
        }
    }
}

让我们看一下输出的第一部分：

comparing 4 and 1...
  checking against 1
    $b  (1) == 1: returning 1

在这里您可以看到它正在检查两个值 4 和 1（我们不知道它是哪个 1）。然后检查 $order 中的每个项目。第一个值是 1，这表示所有 1 必须在任何其他值之前。

$a 不匹配 1 但 $b 匹配。所以这些项目的顺序是错误的 - 第一项大于第二项，所以我们 return 1。即 4 必须在 1 之后。

让我们再看一点输出：

comparing 4 and 2...
  checking against 1
  checking against 3
  checking against 4
    $a (4) == 4: returning 0

这里它检查了值 1 和 3 - 它们都不匹配我们正在考虑的两个数字，因此它们无关紧要。然后我们到达 $a (4)。这等于下一个想要的值。这意味着它在正确的位置，所以我们 return 0。即 4 必须在 2 之前 - 它确实如此。

对排序比较的每一对继续进行。

用 usort() 排序这个数组的机制是什么？

What is the mechanism of ordering this array with usort()?

php

sorting

usort

insertion-sort