使用 PHP 的 uasort 排序时保留键顺序(稳定排序) [英] Preserve key order (stable sort) when sorting with PHP's uasort

问题描述

这个问题实际上是从 SO 上的另一个问题启发而来的，我想稍微扩展一下.

This question is actually inspired from another one here on SO and I wanted to expand it a bit.

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

这是我用来测试可能的解决方案的脚本(还没有找到):

Here is a script I used to test possible solutions (haven't found any):

<?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);
?>

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

Pitfall: Because the keys are ordered in the original array, please don't be tempted to suggest any sorting by key to restore to the original order. I made the example with them ordered to be easier to visually check their order in the output.

推荐答案

自从 PHP 4.1.0 后不支持稳定排序，需要自己编写函数.

Since PHP does not support stable sort after PHP 4.1.0, you need to write your own function.

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

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

As the manual says, "If two members compare as equal, their order in the sorted array is undefined." This means that the sort used is not "stable" and may change the order of elements that compare equal.

有时您确实需要一种稳定的排序.例如，如果您按一个字段对列表进行排序，然后再按另一个字段对其进行排序，但不想丢失前一个字段的排序.在这种情况下，最好将 usort 与一个将两个字段都考虑在内的比较函数一起使用，但如果你不能这样做，那么请使用下面的函数.它是一种合并排序，保证 O(n*log(n)) 复杂度，这意味着即使您使用较大的列表，它也能保持相当快的速度(与冒泡排序和插入排序不同，它们的复杂度为 O(n^2)).

Sometimes you really do need a stable sort. For example, if you sort a list by one field, then sort it again by another field, but don't want to lose the ordering from the previous field. In that case it is better to use usort with a comparison function that takes both fields into account, but if you can't do that then use the function below. It is a merge sort, which is guaranteed O(n*log(n)) complexity, which means it stays reasonably fast even when you use larger lists (unlike bubblesort and insertion sort, which are 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;
}
?>

---

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

---

Also, you may find this forum thread interesting.

这篇关于使用 PHP 的 uasort 排序时保留键顺序(稳定排序)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！