在使用PHP的uasort排序时，保持密钥顺序(稳定排序)

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

这个问题实际上是受到另一个问题的启发所以我想把它展开一点。

Having an associative array in PHP is it possible to sort its values, but where the values are equal to preserve the original key order, using one (or more) of PHP's built in sort function?

在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.

陷阱:因为键是在原始数组中排序的，所以请不要建议按键排序以恢复原始顺序。我用它们做了一个例子，以便更容易地在输出中直观地检查它们的顺序。

6 个解决方案

#1

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

因为PHP 4.1.0之后不支持稳定排序，所以需要编写自己的函数。

This seems to do what you're asking: http://www.php.net/manual/en/function.usort.php#38827

这似乎就是你想要的: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.

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

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)).

有时候你确实需要一个稳定的排序。例如，如果您按一个字段对列表进行排序，然后再按另一个字段对它进行排序，但是不希望丢失来自前一个字段的排序。在这种情况下，最好将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;
}
?>

---

Also, you may find this forum thread interesting.

同样，你可能会发现这个论坛很有趣。

#2

array_multisort comes in handy, just use an ordered range as second array ($order is just temporary, it serves to order the equivalent items of the first array in its original order):

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

Output

输出

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

I used test data with not-ordered keys to demonstrate that it works correctly. Nonetheless, here is the output your test script:

我使用带有无序键的测试数据来证明它是正确的。尽管如此，这里是输出您的测试脚本:

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
)

Downside

It only works with predefined comparisons, you cannot use your own comparison function. The possible values (second parameter of array_multisort()) are:

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

Sorting type flags:

排序类型标志:

• SORT_ASC - sort items ascendingly.
• SORT_ASC -排序项的优势。
• SORT_DESC - sort items descendingly.
• SORT_DESC -后代排序项。
• SORT_REGULAR - compare items normally (don't change types)
• SORT_REGULAR -通常比较项(不要更改类型)
• SORT_NUMERIC - compare items numerically
• SORT_NUMERIC—对项目进行数值比较
• SORT_STRING - compare items as strings
• SORT_STRING——将项作为字符串进行比较
• SORT_LOCALE_STRING - compare items as strings, based on the current locale. It uses the locale, which can be changed using setlocale()
• SORT_LOCALE_STRING——根据当前语言环境将项作为字符串进行比较。它使用语言环境，可以使用setlocale()更改语言环境
• SORT_NATURAL - compare items as strings using "natural ordering" like natsort()
• SORT_NATURAL -使用“自然排序”(如natsort())将项目作为字符串进行比较
• SORT_FLAG_CASE - can be combined (bitwise OR) with SORT_STRING or SORT_NATURAL to sort strings case-insensitively
• SORT_FLAG_CASE—可以(按位或)与SORT_STRING或SORT_NATURAL组合在一起，以不敏感地对字符串进行分类

#3

For future reference, I've put a set of stable sort variants of builtin PHP functions on Github: https://github.com/vanderlee/PHP-stable-sort-functions, based on @Jack's solution and a few other tricks.

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

#4

For completeness sake, you should also check out the Schwartzian transform:

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

The default sort algorithm of PHP works fine with arrays, because of this:

PHP的默认排序算法适用于数组，原因如下:

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

If you want to use your own sorting criteria you can use uasort() as well:

如果您想使用自己的排序标准，也可以使用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
    }
}

#5

This is a solution using which you can achieve stable sort in usort function

这是在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;
}

#6

Just to complete the responses with some very specific case. If the array keys of $array are the default one, then a simple array_values(asort($array)) is sufficient (here for example in ascending order)

用一些非常具体的例子来完成回答。如果$array的数组键是默认键，那么简单的array_values(asort($array))就足够了