非递归快速排序算法实现代码,PHP代码库,德仔网

代码语言

代码分类

【PHP】非递归快速排序算法实现

作者:whiteriver / 发布于2015/8/19/ 757


	<?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, "\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;
	 }
	 }
	}

试试其它关键字

　快速　　排序算法　　非递归　

同语言下

可能有用的

whiteriver贡献的其它代码(4)