logo标签列表

PHP usort的不良行为问题

phpsortingusort
3

我在使用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之前，因为一开始就是这样的。

4个回答
2
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
        )

)

看这里！


这是一个表示惊喜或成功的常用表达，通常用于向别人展示某些事物或成果。在IT技术中，它可能意味着程序员已经成功地解决了一个问题或实现了一项功能。
已接受。不过我用更简洁的方式解决了。在 usort() 之前，我在每个对象中存储了原始数组位置（索引）（即 $data[$i]->original_index = $i），然后在我的比较函数中检查了这个值，当第一个比较返回 0（即相同的排序值）时。相当简单而聪明，不是吗？ :) 谢谢大家！ - lorenzo-s
1
很棒的想法@lorenzo-s。我也这样做了，它完美地运行了，而且使用了更少的自定义代码。 - Jay
1
$compare = strcmp($a['last'], $b['last']);
if ($compare == 0)
    $compare = strcmp($a['name'], $b['name']);
return $compare
请查看我对Tim Cooper回答的评论。 - lorenzo-s
你能给出一个你想要的结果的例子，而不是你正在得到的结果吗？ - Mark Baker
1

你正在寻找一个稳定的排序算法，而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;
});

如果你需要一个稳定的排序，因为现有元素的顺序没有很好地定义，请尝试编写自己的排序算法。例如 冒泡排序非常容易实现。只要你的列表中元素数量相对较小，这是一个很好的解决方案，否则请考虑实现其他稳定的排序算法。

很遗憾，我不知道原始的排序标准（没有）。我不知道有一个精确的定义，用于排序算法的行为如我所述。我看到冒泡排序和归并排序（我最了解的）是稳定的排序...那么... [OT] PHP在内部使用什么算法？！？ - lorenzo-s
PHP使用快速排序算法的一个版本。 - goat
我明白了。他用PHP重写了归并排序，现在（我可以说）它很稳定。目前最佳答案，但我会等一下看看是否有更简洁的想法。 - lorenzo-s
0

试试这个：

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

此函数使用十进制系统的每个数字作为排序标准。排在前面的数字具有最高的位数。可能不是最聪明的方法，但对我来说有效。

和Mark Baker以及Tim Cooper一样。很抱歉，我之前提问的方式有误。我已经更新了。 - lorenzo-s
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接