PHP中如何实现非递归版本的快速排序算法？

本文共计346个文字，预计阅读时间需要2分钟。

php初始化变量 $i 为 100。使用 while 循环，直到 $i 为 0。如果 $i 大于等于 30，则随机选择一个介于 $i-30 和 $i 之间的数字加入数组 $test。否则，随机选择一个介于 1 和 $i 之间的数字加入数组 $test。输出数组 $test 的长度，然后输出换行符。对数组 $test 进行排序，然后使用 implode 函数将数组元素连接成字符串，输出排序后的字符串，并换行。开始计时，使用 quicksort 函数对数组 $test 进行快速排序。

<?php $i = 100; while($i > 0){ if($i > 30){ $test[] = mt_rand($i - 30, $i--); }else{ $test[] = mt_rand(1, $i--); } } //shuffle($test); echo count($test), "\\n"; //sort($test); echo implode(", ", $test), "\\n\\n"; $t1 = microtime(true); quicksort($test); echo implode(", ", $test), "\\n\\n"; echo microtime(true) - $t1, "<br>\\n"; function quicksort(array &$sort){ $end = count($sort); if(--$end < 1){ return; } $beg = 0; $stack = array(); while(true){ $i = $beg; $l = $end; $o = $sort[ $x = mt_rand($i, $l) ]; while($i < $l){ // 左边大于的 if($sort[$i] > $o){ while($i < $l){ // 右边小于等于的 if($sort[$l] <= $o){ $tmp = $sort[$i]; $sort[$i] = $sort[$l]; $sort[$l] = $tmp; $i++; $l--; continue 2; } $l--; } goto re; } $i++; } if($sort[$i] < $o){ $sort[$x] = $sort[$i]; $sort[$i] = $o; } // echo $i, ", ", $l, "; ", $beg, ", ", $end, "\\n"; re: // 保存右边 if($i < $end){ $stack[] = $i; $stack[] = $end; } if(--$i > $beg){ $end = $i; // 继续左边 }elseif($stack){ // 返回继续右边 $end = array_pop($stack); $beg = array_pop($stack); }else{ break; } } }