使用PHP的uasort排序时保留键顺序(稳定排序)

Question

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

陷阱:由于密钥的原始排列有序,请不要试图通过关键建议任何排序恢复到原来的顺序.我用它们做了例子,命令更容易在输出中直观地检查它们的顺序.

Answer 1

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

这似乎就是你所要求的:http://www.php.net/manual/en/function.usort.php#38827

正如手册所说,"如果两个成员相等,那么它们在排序数组中的顺序是不确定的." 这意味着使用的排序不是"稳定的",可能会改变比较相等的元素的顺序.

有时你确实需要稳定的排序.例如,如果您按一个字段对列表进行排序,然后再按另一个字段对其进行排序,但不希望丢失上一个字段的排序.在这种情况下,最好使用带有比较函数的usort来考虑两个字段,但如果你不能这样做,那么使用下面的函数.它是一种合并排序,保证了O(n*log(n))复杂度,这意味着即使使用较大的列表它也会保持相当快(与bubblesort和插入排序不同,它们是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;
}
?>

此外,您可能会发现此论坛帖子很有趣.

Answer 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- 可以与(或按位)组合SORT_STRING或SORT_NATURAL以不区分大小写的方式对字符串进行排序

Answer 3

为了将来参考,我在Github上添加了一组内置PHP函数的稳定排序变体:https://github.com/vanderlee/PHP-stable-sort-functions,基于@Jack 的解决方案和其他一些技巧.

Answer 4

为了完整起见,您还应该查看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
    }
}