usort() 排序算法如何工作？

Question

我有一个 usort() 示例，我添加了一些 echo 语句来查看代码的工作原理：

<?php
function list_cmp($a, $b) {
    global $order;
    echo "$a=$a, $b=$b </br>";

    foreach ($order as $key => $value) {
        echo "$value=$value </br>";
        if ($a == $value) {
            echo "$a=$value, returing 0. </br>";
            return 0;
        }
        if ($b == $value) {
            echo "$b=$value, returing 1. </br>";
            return 1;
        }
    }
}

$order[0] = 1;
$order[1] = 3;
$order[2] = 4;
$order[3] = 2;

$array[0] = 2;
$array[1] = 1;
$array[2] = 3;
$array[3] = 4;
$array[4] = 2;
array[5] = 1;
$array[6] = 2;

usort($array, "list_cmp");
?>

代码的输出是这样的：

$a=2, $b=1 
$value=1 
$b=$value, returing 1. 
$a=2, $b=3 
$value=1 
$value=3 
$b=$value, returing 1. 
$a=1, $b=3 
$value=1 
$a=$value, returing 0. 
$a=2, $b=4 
$value=1 
$value=3 
$value=4 
$b=$value, returing 1. 
$a=3, $b=4 
$value=1 
$value=3 
$a=$value, returing 0. 
$a=2, $b=2 
$value=1 
$value=3 
$value=4 
$value=2 
$a=$value, returing 0. 
$a=2, $b=1 
$value=1 
$b=$value, returing 1. 
$a=2, $b=1 
$value=1 
$b=$value, returing 1. 
$a=4, $b=1 
$value=1 
$b=$value, returing 1. 
$a=3, $b=1 
$value=1 
$b=$value, returing 1. 
$a=1, $b=1 
$value=1 
$a=$value, returing 0. 
$a=2, $b=2 
$value=1 
$value=3 
$value=4 
$value=2 
$a=$value, returing 0.

创建 12 个 $a-$b 对的机制是什么 - 2-1、2-3、1-3、2-4、3-4、2-2、2-1、2- 1（还是一样？）、4-1、3-1、1-1、2-2。上面代码returns1,1,0,1,0,0,1,1,1,1,0,0。根据返回的值对数组进行排序的机制是什么？我试图了解 usort() 机制的工作原理。

谢谢。

Answer 1

比较器是如何工作的？

我不确定这是否是问题的一部分，但要清楚比较器的工作原理：您有一个由有序列表 $order 指定的顺序和一个特殊的 比较器回调 list_cmp 哪个（应该） return 参数

$a 小于 $b（return -1 或值 < 0）
$a 大于 $b（return 1 或值 > 0）
$a 等于 $b (return 0)

list_cmp 通过查找它的 顺序 table 而不是检查

来做到这一点

$a 有一个更小（或相等）的顺序，在这种情况下循环提前退出 return 0 或者如果
$b 有一个较小的顺序，在这种情况下循环提前退出 return 1。

请注意，根据 PHP 文档，这是错误的，它声明它希望 positive/negative/0 作为 return 值。只有当你知道内部只检查 comparator($a,$b) > 0 时，这才是正确的，这意味着它只检查 $b 是否小于且不等于 $a，使之成为一个比较 order of $a <= order of $b.如果代码开始检查 $a 小于和不等于 $b.

，它很容易中断

~~快速排序~~ 排序是如何工作的？

对于初学者，我假设您使用的是 PHP 7 或更高版本。在那种情况下，您会遇到一个特殊情况，其中包含 6-15 个元素大小的数组。 PHP 7+ 似乎不对短列表使用快速排序，而是使用插入排序变体（由于 caching/code 位置等与硬件相关的东西，这很可能更快）。您可以查看排序源代码f.e。在 Github PHP Mirror (as an example: PHP 7.0 Zend/Zend_sort.c Line 177-198) 上。

代码分 3 个步骤运行：

比较：比较相邻元素array[j]和array[j+1]，如果array[j] <= array[j+1]继续，否则转到2.
找到插入点：现在如果array[j] > array[j+1]，向后扫描找到array[x] < array[j+1] <= array[x+1]为x < j的点（显然只有x 开始）
insert: 将元素 x+1 ... j 向上移动，使其变为 x+2 ... j+1 并在 x+1[=98= 位置插入前一个元素]

如果将该代码应用于配对 (2-1、2-3、1-3、2-4、3-4、2-2、2-1、2-1、4-1、 3-1、1-1、2-2) 代码的作用显而易见。

-- [2,1],3,4,2,1,2 -> 1./2./3. compare [2,1], find and insert 1 before 2
-- 1,[2,3],4,2,1,2 -> 1./2. compare [2,3], find insert point for 3 (since order of 3 < order of 2)
-- [1,3],2,4,2,1,2 -> 3. compare [1,3], found insert point for 3 before 2
-- 1,3,[2,4],2,1,2 -> 1./2. compare [2,4], find insert point for 4 (since order of 4 < order of 2) 
-- 1,[3,4],2,2,1,2 -> 3. compare [3,4], found insert point for 4 before 2
-- 1,3,4,[2,2],1,2 -> 1. compare [2,2], skip
-- 1,3,4,2,[2,1],2 -> 1./2. compare [2,1], find insert point for 1
-- 1,3,4,[2,1],2,2 -> 2. compare [2,1], find insert point for 1
-- 1,3,[4,1],2,2,2 -> 2. compare [4,1], find insert point for 1
-- 1,[3,1],4,2,2,2 -> 2. compare [3,1], find insert point for 1
-- [1,1],3,4,2,2,2 -> 3. compare [1,1], fond insert point for 1 before 3
-- 1,1,3,4,2,[2,2] -> 1. compare [2,2], skip
-- sorted: 1,1,3,4,2,2,2

PS: 在这里您已经看到，即使是一个简单的排序算法（22 行代码），通过其比较模式来推导工作也是相当复杂的。 PHP 7 quicksort 实现的代码行大约是原来的 10 倍，并且有一些奇怪的优化（除了由于基准选择和递归引起的正常疯狂之外）。

大多数情况下，最好忽略深入的实现细节，只将其简化为需要的东西。排序算法的典型问题是它是否为 stable/unstable 并且在 O(log n) 中执行且内存消耗为 O(n)。有更简单的方法来学习这些优化实现背后的核心算法，例如 Quicksort Dance 或任何其他可视化或带有示例的旧（电子）书或网页。

-- 已编辑

添加了一个（不好的、未优化的、不安全的）php 插入排序的实现，以另一种可视化它是如何工作的：

<?php

function my_usort($A, $comparator) {
  // Start .. End Positions
  $current_pos = 0;
  $last_pos = count($A)-1;
  // Outer Loop: each step checks that A[0] up to A[current_pos] is sorted. 
  // When the algorithm finishes we know that A[0] ... A[last_pos] is sorted
  while($current_pos < $last_pos) {
    echo "Sorted Subarray from $A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n";
    echo "$A looks like this now: " . json_encode($A) . 
    ", comparing [" . $A[$current_pos] . "," . $A[$current_pos +1] . "] (verify step)<br>\n";
    // "Verification Step"
    // At this point A[0] ... A[current_pos] is sorted.
    // Check A[current_pos] <= A[current_pos +1]
    if($comparator($A[$current_pos], $A[$current_pos +1]) > 0) {
      // nope, A[current_pos] > A[current_pos +1] (list_cmp/comparator returns value > 0)
      // "Insertion Step" start, find the correct position for A[current_pos+1] in the already
      // sorted list A[0] ... A[current_pos]
      $insert_point = $current_pos;
      // Swap the missmatching Neighbor pair
      echo "swapping: $A[" . $insert_point . "] and $A[" . ($insert_point+1) . "]<br>\n";
      $tmp = $A[$insert_point +1];
      $A[$insert_point +1] = $A[$insert_point];
      $A[$insert_point] = $tmp;
      $sorted_up_to_current_pos = false;
      // Inner Loop: find correct insertion point
      while($insert_point > 0 && !$sorted_up_to_current_pos) {
        echo "$A looks like this now: " . json_encode($A) . 
        ", comparing [" . $A[$insert_point-1] . "," . $A[$insert_point] . "] (insertion step)<br>\n";
      // "Insertion Step", Swap the missmatching Neighbor pairs until A[0] ... A[current_pos] is sorted again
      if($comparator($A[$insert_point-1], $A[$insert_point]) > 0) {
          // Swap the missmatching Neighbor pair
          echo "swapping: $A[" . ($insert_point-1) . "] and $A[" . $insert_point . "]<br>\n";
          $tmp = $A[$insert_point];
          $A[$insert_point] = $A[$insert_point-1];
          $A[$insert_point-1] = $tmp;
          // goto new pair
          $insert_point = $insert_point -1;
        } else {
          // found correct spot, done
          $sorted_up_to_current_pos = true;
        }
      }
      $A[$insert_point] = $tmp;
      echo "$A looks like this now: " . json_encode($A) . ", insertion done<br>\n";
    }
    $current_pos = $current_pos + 1;
  }
  echo "Sorted Array $A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n";
}

function list_cmp($a, $b) {
  global $order;
  //echo "$a=$a, $b=$b </br>\n";

  foreach ($order as $key => $value) {
      //echo "$value=$value </br>\n";
      if ($a == $value) {
          echo "$a=$value, returing 0. </br>\n";
          return 0;
      }
      if ($b == $value) {
          echo "$b=$value, returing 1. </br>\n";
          return 1;
      }
  }
}

$order[0] = 1;
$order[1] = 3;
$order[2] = 4;
$order[3] = 2;

$array[0] = 2;
$array[1] = 1;
$array[2] = 3;
$array[3] = 4;
$array[4] = 2;
$array[5] = 1;
$array[6] = 2;

my_usort($array, "list_cmp");

输出现在已完成，当前排序的数组位置：

Sorted Subarray from $A is [2] 
$A looks like this now: [2,1,3,4,2,1,2], comparing [2,1] (verify step) 
$b=$value, returing 1.  
swapping: $A[0] and $A[1] 
$A looks like this now: [1,2,3,4,2,1,2], insertion done 
Sorted Subarray from $A is [1,2] 
$A looks like this now: [1,2,3,4,2,1,2], comparing [2,3] (verify step) 
$b=$value, returing 1.  
swapping: $A[1] and $A[2] 
$A looks like this now: [1,3,2,4,2,1,2], comparing [1,3] (insertion step) 
$a=$value, returing 0.  
$A looks like this now: [1,3,2,4,2,1,2], insertion done 
Sorted Subarray from $A is [1,3,2] 
$A looks like this now: [1,3,2,4,2,1,2], comparing [2,4] (verify step) 
$b=$value, returing 1.  
swapping: $A[2] and $A[3] 
$A looks like this now: [1,3,4,2,2,1,2], comparing [3,4] (insertion step) 
$a=$value, returing 0.  
$A looks like this now: [1,3,4,2,2,1,2], insertion done 
Sorted Subarray from $A is [1,3,4,2] 
$A looks like this now: [1,3,4,2,2,1,2], comparing [2,2] (verify step) 
$a=$value, returing 0.  
Sorted Subarray from $A is [1,3,4,2,2] 
$A looks like this now: [1,3,4,2,2,1,2], comparing [2,1] (verify step) 
$b=$value, returing 1.  
swapping: $A[4] and $A[5] 
$A looks like this now: [1,3,4,2,1,2,2], comparing [2,1] (insertion step) 
$b=$value, returing 1.  
swapping: $A[3] and $A[4] 
$A looks like this now: [1,3,4,1,2,2,2], comparing [4,1] (insertion step) 
$b=$value, returing 1.  
swapping: $A[2] and $A[3] 
$A looks like this now: [1,3,1,4,2,2,2], comparing [3,1] (insertion step) 
$b=$value, returing 1.  
swapping: $A[1] and $A[2] 
$A looks like this now: [1,1,3,4,2,2,2], comparing [1,1] (insertion step) 
$a=$value, returing 0.  
$A looks like this now: [1,1,3,4,2,2,2], insertion done 
Sorted Subarray from $A is [1,1,3,4,2,2] 
$A looks like this now: [1,1,3,4,2,2,2], comparing [2,2] (verify step) 
$a=$value, returing 0.  
Sorted Array $A is [1,1,3,4,2,2,2]

usort() 排序算法如何工作？

How the usort() sorting algorithm works?

php

quicksort

usort