排序算法

算法就是事物的一种规律

//问: 如果有100个灯,走一次就关闭自己的倍数的灯,  然后+1 重新走 再次按倍数的关灯  到100个灯的时候这个灯是亮的还是关闭的
//答: 与自己走过的次数取模成功 然后累加取模成功的数量,再次与2取模如果成功那么就是亮的否则就是关闭的
function light($num)
{
	$a = 1;
	
	for ($i=1; $i <= $num$i++) { 
		echo '<div style="width:20px;height:20px;background-color:#faa2f2;float:left;margin-left:10px"></div>';
	}
	echo '<br /><hr />';
	//$color = array('#f2f2f2','#a2a2a2');
	for ($z=1; $z <= $num$z++) { 
		for ($x=1; $x <= $z$x++) { 
			if ($z%$x == 0) {
				@$sum[$z] += 1;
			}
			//echo '<div style="width:20px;height:20px;background-color:#000;float:left;margin-left:10px"></div>';
		}
		for ($j=$z$j <= $num$j++) { 
			if($j%$z == 0){
				$color = '#f2f2f2';
			}else{
				$color = '#faa2f2';
			}
			//echo '<div style="width:20px;height:20px;background-color:'.$color.';float:left;margin-left:10px">'.$j.'</div>';
		}
		
		if($sum[$z]%2 == 0){
			//echo '第'.$z.'次亮的';
			$last = '第'.$z.'次亮的';
		}else{
			$last = '第'.$z.'次不亮的';
		}
		//echo '<br /><br />';
	}

	echo $last;
}

light(16); //求第十六次灯是否亮的

冒泡排序算法 

    //由小往大排序 冒泡
    public function bubble_sort($arr) {
        $n=count($arr);
            for($i=0;$i<$n-1;$i++){
                for($j=$i+1;$j<$n;$j++) {
                    if($arr[$j]<$arr[$i]) {
                        $temp=$arr[$i];
                        $arr[$i]=$arr[$j];
                        $arr[$j]=$temp;
                    }
                }
            }
        return $arr;
    }
环境 WampServer Version 2.5  框架 onethink1

        # 3000 数据 字段 uid,nickname 用时 1.492003267   
        # 6000 数据 用时 5.957014533               4.9290100
        # 9000 数据 用时 13.890031832  只有一个字段 11.3481670

    快速排序法

function quick_sort($arr) {
$n=count($arr);
if($n<=1)
return $arr;
$key=$arr[0];
$left_arr=array();
$right_arr=array();
for($i=1;$i<$n;$i++) {
if($arr[$i]<=$key)
$left_arr[]=$arr[$i];
else
$right_arr[]=$arr[$i];
}
$left_arr=quick_sort($left_arr);
$right_arr=quick_sort($right_arr);
return array_merge($left_arr,array($key),$right_arr);
}

在 WampServer Version 2.5  环境中

 ini_set('xdebug.max_nesting_level'2000); #递归次数设置在 2000次,但实际上只到400多点  , 再多就会被限制
 
 测试在 300条数据运行时间为  0.02600128 s

关于递归: 逻辑上的递归可以无次数限制, 但语言执行器或者程序堆栈会限制递归的次数.

 

  插入排序  维基百科

    public function insertSort($arr) {
        $n=count($arr);
            for($i=1;$i<$n;$i++) {
            $tmp=$arr[$i];
            $j=$i-1;
                while($arr[$j]>$tmp) {
                    $arr[$j+1]=$arr[$j];
                    $arr[$j]=$tmp;
                    $j--;
                    if($j<0)
                        break;
                }
            }
        return $arr;
    }
    
算法思路
1.从第一个元素开始,该元素可以认为已经被排序
2.取出下一个元素,在已经排序的元素序列中从后向前扫描
3.如果该元素(已排序)大于新元素,将该元素移到下一位置
4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
重复步骤2~5

#实验结果 与冒泡与快速排序相比 同样环境中  同样数据 9000条
冒泡耗时: 13s
插入耗时: <1s

发表评论