PHP usort()在相等情况下的排序顺序

Question

在PHP的usort()手册中，它声明：

如果两个成员比较相等，则它们在排序数组中的相对顺序是未定义的。

另外，

引入了一种新的排序算法。cmp_function不会为比较相等的元素保留原始顺序。

那么我的问题是：如果两个元素相等（例如用户定义的函数返回0），会发生什么？

我正在使用此函数，显然相等的项目随机排列在排序后的数组中。

- linkyndy

---

你的意思是它们在其他相等的值中随机排列吗？当然它们不会随机插入到已排序的集合中的任何位置。 - Mike B

我不理解这个问题......你自己已经回答了：相等元素的顺序是没有定义的。 - erisco

那么如果没有定义，相等的元素是如何排列在数组中的呢？这就是我不理解的地方。 - linkyndy

@linkyndy 看起来相等的项被附加在其他相等的项之后。 - Mike B

对我来说也是这样，我想要确定一下。 - linkyndy

Answer 1

请注意不要混淆“未定义”和“随机”。

实现一个随机算法确实会期望每次都给出不同的排序顺序。这意味着在发现它们相等时，需要特定的代码来洗牌结果。这将使算法更加复杂和缓慢，并且很少是一种理想的结果。

而未定义的含义恰好相反：在设计算法时没有采取任何措施来保证可预测或稳定的顺序。这意味着结果可能每次运行时都会不同，如果那恰好是该数据在算法中的副作用。

你可以在PHP源代码中看到核心排序实现。它由“快速排序”（分而治之）和插入排序（一种适用于短列表的简单算法）混合组成，并带有用于2、3、4和5个元素列表的手动优化例程。

因此，相等成员的确切行为将取决于诸如列表大小、这些相等成员在列表中的位置、一批中有多少相等成员等因素。在某些情况下，算法将看到它们是相同的，并且不会交换它们（这是理想的，因为交换需要时间）；在其他情况下，它不会直接比较它们，直到它们已经相对于其他事物移动了位置，因此它们将以不同的顺序结束。

- IMSoP

Answer 2

在对我的数组进行排序时，我也发现了同样的问题，于是我找到了一些自定义函数，因为php有一些限制，不能使用已定义的sorting函数。

http://php.net/manual/en/function.uasort.php#Vd114535

PHP 7对小型数组（<16）使用稳定的排序算法， 但对于较大的数组，该算法仍然不稳定。 此外，PHP不能保证使用*sort()进行排序是否稳定https://bugs.php.net/bug.php?id=53341。

- Muneer Alam

Answer 3

这个函数对于相等的值保持顺序（来自我的CMS EFFCORE的示例）：

function array_sort_by_number(&$array, $key = 'weight', $order = 'a') {
  $increments = [];
  foreach ($array as &$c_item) {
    $c_value = is_object($c_item) ? $c_item->{$key} : $c_item[$key];
    if ($order === 'a') $increments[$c_value] = array_key_exists($c_value, $increments) ? $increments[$c_value] - .0001 : 0;
    if ($order === 'd') $increments[$c_value] = array_key_exists($c_value, $increments) ? $increments[$c_value] + .0001 : 0;
    if (is_object($c_item)) $c_item->_synthetic_weight   = $c_value + $increments[$c_value];
    else                    $c_item['_synthetic_weight'] = $c_value + $increments[$c_value];
  }
  uasort($array, function ($a, $b) use ($order) {
    if ($order === 'a') return (is_object($b) ? $b->_synthetic_weight : $b['_synthetic_weight']) <=> (is_object($a) ? $a->_synthetic_weight : $a['_synthetic_weight']);
    if ($order === 'd') return (is_object($a) ? $a->_synthetic_weight : $a['_synthetic_weight']) <=> (is_object($b) ? $b->_synthetic_weight : $b['_synthetic_weight']);
  });
  foreach ($array as &$c_item) {
    if (is_object($c_item)) unset($c_item->_synthetic_weight);
    else                    unset($c_item['_synthetic_weight']);
  }
  return $array;
}

它适用于数组和对象。 它添加了一个合成键，按照该键排序，然后将其删除。

测试

$test = [
  'a' => ['weight' =>  4],
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
  'e' => ['weight' =>  4],
];
$test_result = [
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
  'a' => ['weight' =>  4],
  'e' => ['weight' =>  4],
];
array_sort_by_number($test, 'weight', 'a');
print_R($test);
var_dump($test === $test_result);

$test = [
  'a' => ['weight' =>  4],
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
  'e' => ['weight' =>  4],
];
$test_result = [
  'a' => ['weight' =>  4],
  'e' => ['weight' =>  4],
  'b' => ['weight' => 10],
  'c' => ['weight' => 10],
  'd' => ['weight' => 10],
];
array_sort_by_number($test, 'weight', 'd');
print_R($test);
var_dump($test === $test_result);

- Maxim Rysevets

Answer 4

我也遇到了同样的问题，其中有2行具有相同的值，当应用排序函数时，它们的顺序会改变，而我不想要这种情况。我想根据它们的值对键进行排序，如果它们相等，则不更改顺序。所以这是我的解决方案-

// sample array 
$arr = Array("a" => 0.57,"b" => 1.19,"c" => 0.57,"d" => 0.57,"e" => 0.57,"f" => 0.57,"g" => 0.57,"h" => 0.57,"i" => 0.99,"j" => 1.19,"k" => 1.19);
    $multi_arr = [];
    foreach ($arr as $k=>$val){
       $multi_arr["$val"][] = array($k=>$val); 
    }
    uksort($multi_arr, function ($a, $b) { 
                    return $b > $a ? 1 : -1;
            });
    $s_arr = [];
    foreach ($multi_arr as $k=>$val){
        foreach($val as $p_id){         
            $p_arr = array_keys($p_id);
            $s_arr[] = $p_arr[0]; 
        }
    }
print_r($s_arr);

输出-

数组([0] => b,[1] => j,[2] => k,[3] => i,[4] => a,[5] => c,[6] => d,[7] => e,[8] => f,[9] => g,[10] => h)

- user3391295

Answer 5

了解PHP在比较值相同时不关心顺序。

例如：

$temp=array("b"=>"10","c"=>"10","d"=>"10","e"=>"4");

如上所示，该数组有4个元素，其中3个具有相同的值，如b、c、d=10；arsort() // arsort()函数按值降序对关联数组进行排序

如果print_r(arsort($temp))输出：=> Array ( [b] => 10 [c] => 10 [d] => 10 [e] => 4 )

这意味着它返回排序后的等值数组，但保持相等值的位置（顺序）不变

但是

如果$temp=array("a"=>"4",b"=>"10","c"=>"10","d"=>"10","e"=>"4"); 在上述数组中，b、c、d=10被限制在两个极端的左右数组中，其值小于中心(b、c、d=10)的值。

以上tmp的arsort输出为： Array ( [c] => 10 [b] => 10 [d] => 10 [a] => 4 [e] => 4 )

它给出了中间部分即[c]数组在中心。 这意味着，如果相似值或相等值的数组被低值数组从两侧限制，或者第一个值比顺序低，则相等值的顺序将从三个数组值中的第一个作为中间值。

- Shashikant Kuswaha

Answer 6

如果我有一个数组：['b', 'a', 'c', 'b']，并对其进行排序，那么会得到：['a'，'b'，'b'，'c']。由于'b' == 'b'，php无法保证哪个排在前面，因此排序顺序是“未定义的”，但由于它们相等，这是否重要？

如果您使用的排序函数对不相等的对象返回0，则面临完全不同的问题。

- Alexander Varwijk

---

我正在使用 usort() 按每个数组中元素的数量进行排序。因此，如果我有 0=>(1, 2), 1=>(1, 3), 2=>(1, 2), 3=>(1, 3)，则顺序变为 2=>(1, 2), 1=>(1, 3), 3=>(1, 3), 0=>(1, 2)，我想知道为什么 0 被移到了最后。 - linkyndy

我不确定那个，脑海中浮现的第一件事是“看看你的键盘，0在最后”，但那似乎毫无关联;) 在多次迭代中，顺序是否相同？如果行为确实是“未定义的”，每次都应该产生不同的顺序。 如果我的基本排序算法理解正确，将0移动到源数组中也会将其移动到结果数组中的另一个位置。 - Alexander Varwijk

多次迭代后，顺序仍然相同，因此即使在相等元素之间也必须进行某种排序。我会深入挖掘并发布我的结果。谢谢你的帮助 :) - linkyndy

我知道这个问题很老了，但你有找到解决方法吗？ - Emyr Thomas