使用 PHP 的 uasort 进行排序时保留键顺序（稳定排序）

php arrays algorithm sorting

2022-08-30 17:02:28

这个问题实际上是从SO上的另一个问题中启发的，我想扩展一下。

在PHP中有一个关联数组是否可以对其值进行排序，但是在值相等的情况下，使用一个（或多个）PHP的内置排序函数来保留原始键顺序？

以下是我用来测试可能的解决方案的脚本（尚未找到任何脚本）：

<?php
header('Content-type: text/plain');
for($i=0;$i<10;$i++){
    $arr['key-'.$i] = rand(1,5)*10;
}
uasort($arr, function($a, $b){
    // sort condition may go here //
    // Tried: return ($a == $b)?1:($a - $b); //
    // Tried: return $a >= $b; //
});
print_r($arr);
?>

陷阱：由于密钥在原始数组中排序，因此请不要试图建议按密钥排序以恢复到原始顺序。我用它们的顺序制作了示例，以便更容易直观地检查它们在输出中的顺序。

答案 1

由于 PHP 在 PHP 4.1.0 之后不支持稳定排序，因此您需要编写自己的函数。

这似乎符合您的要求：http://www.php.net/manual/en/function.usort.php#38827

正如手册所说，“如果两个成员的比较相等，则它们在排序数组中的顺序是未定义的。这意味着使用的排序不是“稳定的”，并且可能会改变比较相等的元素的顺序。

有时你真的需要一个稳定的排序。例如，如果按一个字段对列表进行排序，则按另一个字段再次排序，但不希望丢失上一个字段的顺序。在这种情况下，最好将 usort 与将两个字段都考虑在内进行比较函数，但如果不能这样做，请使用下面的函数。它是一种合并排序，保证 O（n*log（n））复杂性，这意味着即使您使用较大的列表，它也能保持相当快的速度（与气泡排序和插入排序不同，它们是 O（n^2））。

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

另外，您可能会发现这个论坛帖子很有趣。

答案 2

array_multisort派上用场，只需使用有序范围作为第二个数组（只是临时的，它用于按其原始顺序对第一个数组的等效项进行排序）：$order

$a = [
  "key-0" => 5,
  "key-99" => 3,
  "key-2" => 3,
  "key-3" => 7
];

$order = range(1,count($a));
array_multisort($a, SORT_ASC, $order, SORT_ASC);

var_dump($a);

输出

array(4) {
  ["key-99"]=>
  int(3)
  ["key-2"]=>
  int(3)
  ["key-0"]=>
  int(5)
  ["key-3"]=>
  int(7)
}

我使用带有无序键的测试数据来证明它工作正常。不过，下面是测试脚本的输出：

Array
(
    [key-1] => 10
    [key-4] => 10
    [key-5] => 20
    [key-8] => 20
    [key-6] => 30
    [key-9] => 30
    [key-2] => 40
    [key-0] => 50
    [key-3] => 50
    [key-7] => 50
)

缺点

它仅适用于预定义的比较，您不能使用自己的比较函数。可能的值（的第二个参数）为：array_multisort()

排序类型标志：

SORT_ASC- 按升序对项目进行排序。

SORT_DESC- 按顺序对项目进行排序。

SORT_REGULAR- 正常比较项目（不要更改类型）

SORT_NUMERIC- 以数字方式比较项目

SORT_STRING- 将项目作为字符串进行比较

SORT_LOCALE_STRING- 根据当前区域设置将项目作为字符串进行比较。它使用区域设置，可以使用以下命令进行更改setlocale()

SORT_NATURAL- 使用“自然排序”将项目作为字符串进行比较，例如natsort()

SORT_FLAG_CASE- 可以组合（按位 OR）或以不区分大小写的字符串进行排序SORT_STRINGSORT_NATURAL