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

一尘不染

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

algorithm

这个问题实际上是从另一个关于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);
?>

陷阱：由于密钥是按原始数组排序的，因此请不要试图建议按密钥进行任何排序以恢复原始顺序。我将它们排序为示例，以便更直观地查看输出中的顺序。

阅读 244

2020-07-28

共1个答案

一尘不染

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

这似乎可以满足您的要求：http :
//www.php.net/manual/zh/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;
}
?>

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

2020-07-28