PHP 中的 Bogo 排序
前几天我遇到了这种称为“bogosort”的排序算法。这是一种笑话排序算法,在实际排序数组时非常无效。这个名字来自“假”这个词。
下面是它的工作原理。
取一个数组。
洗牌吧。
如果数组已排序,则停止。
如果数组未排序,则返回步骤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';
很长一段时间后,这是打印出来的。
Totaltime:897.42127370834sAveragetimepersort:81.583752155304
对10个包含10个项目的数组进行排序需要整整15分钟。