PHP 中的 Bogo 排序

前几天我遇到了这种称为“bogo sort”的排序算法。这是一种笑话排序算法，在实际排序数组时非常无效。这个名字来自“假”这个词。

下面是它的工作原理。

1. 取一个数组。

2. 洗牌吧。

3. 如果数组已排序，则停止。

4. 如果数组未排序，则返回步骤 2。

如您所见，这与其说是一种排序算法，不如说是一种机会游戏。由于排序的随机性，您可能需要等待很长时间才能真正对数组进行排序。

这是 PHP 中 bogo 排序的实现。

/**
 * Sort an array using a bogo sort algorithm.
 *
 * @param array $array
 *  The array to sort.
 *
 * @return array
 *   The sorted array.
 */
function bogoSort($array) {
  // 假设数组未排序。
  $sorted = FALSE;
 
  while ($sorted == FALSE) {
    // 继续运行直到数组排序。
    for ($i = 0; $i < count($array) - 1;++$i) {
      // 循环遍历数组并检查它是否已排序。
      if ($array[$i] > $array[$i + 1]) {
        // 数组尚未排序，因此跳出检查循环。
        $sorted = FALSE;
        break;
      }
      // 如果我们到达这一点，则数组已排序。
      $sorted = TRUE;
    }
 
    if ($sorted) {
      // 数组已排序，返回。
      return $array;
    }
 
    // 打乱数组。
    shuffle($array);
  }
}

那么为什么要做这个呢？真的只是为了好玩。当我第一次听说这种排序算法时，我笑得很开心，所以我必须有一个上帝来实现它。该算法通常用于教育目的，作为最坏的情况。bogo 排序通常比单向冒泡排序慢。

bogo 排序的机制意味着数组的长度会显着增加排序所需的时间。对少于 5 个项目的数组进行排序需要几秒钟（实际上还是很长的时间）。对超过 10 个项目的数组进行排序需要几分钟时间。我没有在数组中测试超过 10 个项目，因为我将等待很长时间进行排序。

作为一个快速测试，我决定看看 bogo 排序实际需要多长时间。 

$times = [];
 
for ($i = 0; $i <= 10; ++$i) {
  $time_start = microtime(true);
 
  $array = range(0, 10);
  shuffle($array);
  $array = bogoSort($array);
 
  $time_end = microtime(true);
  $times[] = $time_end - $time_start;
}
echo 'Total time: ' . (array_sum($times)) . 's Average time per sort: ' . (array_sum($times) / count($times)) . 's';

很长一段时间后，这是打印出来的。

Total time: 897.42127370834s Average time per sort: 81.583752155304

对 10 个包含 10 个项目的数组进行排序需要整整 15 分钟。