logo标签列表

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

phpquicksortusort
4

我有一个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）的机制是什么？上述代码返回1,1,0,1,0,0,1,1,1,1,0,0。另外，根据返回的值对数组进行排序的机制是什么？我正在尝试理解usort()的机制。
谢谢。
sort() 函数使用的是快速排序算法，文档似乎暗示了 PHP 中的大多数其他排序方法也使用相同的算法。 - apokryfos
也许这个快速排序的动画解释可以帮到你：http://me.dt.in.th/page/Quicksort/ - Mark Baker
1
你的排序函数有问题。如果两个元素具有相同的排序值，则应返回0。如果第一个元素具有更高的排序值，则应返回正值。如果第二个元素具有更高的排序值，则应返回负值。 - GordonM
1个回答
6
  1. 比较器是如何工作的？

我不确定这是否是问题的一部分，但为了明确比较器的工作原理：

您有一个由有序列表$order指定的顺序和一个特殊的比较回调list_cmp，它（应该）返回参数

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

list_cmp通过查找其顺序表来执行此操作，并检查是否

  • $a具有更小的（或相同的）顺序，在这种情况下，循环使用return 0提前退出，或者如果
  • $b具有更小的顺序，在这种情况下，循环使用return 1提前退出。

请注意，根据PHP文档，这是错误的，因为它希望返回正/负/0作为返回值。只有当您知道内部仅检查comparator($a,$b) > 0时，这才是正确的，这意味着它只检查$b是否小于而不等于$a，使得比较$a<= $b的顺序。如果代码开始检查$a是否小于且不等于$b，它很容易出错。

  1. 快速排序（quicksort）排序是如何工作的？

首先，我假设您正在使用PHP 7或更高版本。在这种情况下，对于6-15个元素大小的数组，您遇到了一个特殊情况。PHP 7+似乎不使用快速排序来排序短列表，而是使用插入排序变体（由于硬件相关的东西，如缓存/代码局部性，它可能更快）。您可以在Github PHP Mirror中检查排序源代码（例如：PHP 7.0 Zend/Zend_sort.c Line 177-198）。

该代码分为3个步骤：

  1. 比较：比较相邻元素array[j]和array[j+1]，如果array[j] <= array[j+1]则继续，否则转到步骤2。
  2. 查找插入点：如果现在array[j] > array[j+1]，向后扫描以找到一个位置，在该位置之前的x满足array[x] < array[j+1] <= array[x+1]（很明显只需要向前扫描直到x达到起始位置）
  3. 插入：将元素x+1 ... j上移一位，使其变为x+2 ... j+1，并将原来的元素插入到位置x+1

如果将该代码应用于配对(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

注意：这里可以看到，即使是一个简单的排序算法（22行代码），也很难通过比较模式来推导出它的工作方式。PHP 7快速排序实现的代码行数约为原始版本的10倍，并且有一些疯狂的优化（除了由于选择枢轴和递归而产生的正常疯狂）。

大多数情况下，最好忽略深度实现细节，只减少到所需的内容。对于排序算法的典型问题是它是否稳定/不稳定，并以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]
非常感谢您提供的信息。如果没有这些信息，我可能需要一周或更长时间才能达到这个知识点。数组在排序过程完成之前不会改变，这种说法正确吗？您描述了排序过程，但是当我在运行代码的某些时刻使用var_dump函数查看数组时，它总是相同的。 - now_m
我仍然不明白这是如何工作的。有$order数组，它与$a-$b对进行比较。唯一的机制在于当list_cmp函数返回1时，当前的$b值会向数组的开头移动（较低的索引；始终为$b且始终朝这个方向）。如果list_cmp回调返回1，那么是什么“运行”了找到$b正确位置的机制？这是内置在usort()中的吗？可能不是，因为我们不是创建像1,2,3,4,5,6,7,8,9这样的东西，而是像这样的东西1,1,3,4,2,2,2。 - now_m
@now_m 我不确定您是对算法还是整个排序顺序理论有问题。算法部分很简单。它只是从“左侧”（最低索引）到“右侧”（最高索引）检查每个相邻的一对是否按顺序排列（并且list_cmp定义了此顺序）。如果它遇到不符合条件的一对（list_cmp返回1），则将右侧元素向左移动并再次与其新的左侧进行检查。这将继续进行，直到它符合条件（list_cmp返回0）或达到列表开头。没有什么魔法。 - makadev
非常感谢！您似乎是一个非常熟悉这方面的人，而我只是在学习 PHP 的第二轮（我计划学习十轮）。再次感谢您的解释。这是我遇到的最难的例子。正如您所看到的，我仍在摸索中，但可能今天就能结束了。再次感谢！ - now_m
1
@now_m 我选择了简单的道路，学习了IT。;) 除了其他课程中的数学和编程基础知识外，我们还有一门课程（半年，每周约8小时和作业），介绍了基本的数据结构和算法，如排序、“分而治之”的原理、列表/树形数据结构、证明正确性以及运行时间/内存的复杂度。我只能想象在纯自学中这是多么困难。不要离题太远：这门课程通常被称为“算法导论”，你可能想要查看一下。除了一些（昂贵的）书籍外，还有许多免费的网络资源。 - makadev
显示剩余10条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接