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

问题描述 投票：0回答：7

这个问题实际上是受到 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);
?>

陷阱：因为键是在原始数组中排序的，所以请不要试图建议按键进行任何排序以恢复到原始顺序。我用它们制作了示例，以便更容易在输出中直观地检查它们的顺序。

php arrays algorithm sorting
7个回答
28
投票

由于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;
}
?>

此外，您可能会发现此论坛主题很有趣。

11
投票

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
    - 可以与 
    SORT_STRING
    或 
    SORT_NATURAL
    组合（按位或）来对字符串进行不区分大小写的排序
5
投票

为了完整起见，您还应该查看 Schwartzian 变换：

// decorate step
$key = 0;
foreach ($arr as &$item) {
        $item = array($item, $key++); // add array index as secondary sort key
}

// sort step
asort($arr); // sort it

// undecorate step
foreach ($arr as &$item) {
    $item = $item[0]; // remove decoration from previous step
}

PHP 的默认排序算法可以很好地处理数组，因为：

array(1, 0) < array(2, 0); // true
array(1, 1) < array(1, 2); // true

如果您想使用自己的排序标准，您也可以使用

uasort()
：

// each parameter is an array with two elements
// [0] - the original item
// [1] - the array key
function mysort($a, $b)
{
    if ($a[0] != $b[0]) {
        return $a[0] < $b[0] ? -1 : 1;
    } else {
        // $a[0] == $b[0], sort on key
        return $a[1] < $b[1] ? -1 : 1; // ASC
    }
}
1
投票

这是一个可以在 usort 函数中实现稳定排序的解决方案

public function sortBy(array &$array, $value_compare_func)
{
    $index = 0;
    foreach ($array as &$item) {
        $item = array($index++, $item);
    }
    $result = usort($array, function($a, $b) use ($value_compare_func) {
        $result = call_user_func($value_compare_func, $a[1], $b[1]);
        return $result == 0 ? $a[0] - $b[0] : $result;
    });
    foreach ($array as &$item) {
        $item = $item[1];
    }
    return $result;
}
0
投票

作为稳定排序的解决方法：

<?php
header('Content-type: text/plain');
for ($i = 0;$i < 10;$i++)
{
    $arr['key-' . $i] = rand(1, 5) * 10;
}
uksort($arr, function ($a, $b) use ($arr)
{
    if ($arr[$a] === $arr[$b]) return array_search($a, array_keys($arr)) - array_search($b, array_keys($arr));
    return $arr[$a] - $arr[$b];
});
print_r($arr);
0
投票

从 PHP8.0 开始，整个页面都已过时。 PHP 执行稳定的排序。

鉴于：

$array = array (
  'key-0' => 40,
  'key-1' => 50,
  'key-2' => 10,
  'key-3' => 20,
  'key-4' => 20,
  'key-5' => 30,
  'key-6' => 10,
  'key-7' => 20,
  'key-8' => 40,
  'key-9' => 40,
);


asort()
：（演示）

asort($array);
var_export($array);


uasort()
：（演示）

uasort($array, fn($a, $b) => $a <=> $b);
var_export($array);

输出（来自任一）：

array (
  'key-2' => 10,
  'key-6' => 10,
  'key-3' => 20,
  'key-4' => 20,
  'key-7' => 20,
  'key-5' => 30,
  'key-0' => 40,
  'key-8' => 40,
  'key-9' => 40,
  'key-1' => 50,
)

请注意，现在，值按值升序排序，原始键保留在其原始位置 - 相对于具有相同值的其他元素。

-1
投票

只是为了用一些非常具体的案例来完成回答。如果 

$array
的数组键是默认键，那么一个简单的 
array_values(asort($array))
就足够了（这里以升序为例）

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.