[TOC] ## 冒泡排序 O(n2) ``` 依次对比相邻的值，符合条件(大于或小于)则交换位置 function sort_maopao($array){ if(count($array) <= 1){ return $array; } $num = count($array); for($i=0;$i<$num;$i++){ for($j=0;$j<$num-$i-1;$j++){ if($array[$j] > $array[$j+1]){ list($array[$j],$array[$j+1]) = [$array[$j+1],$array[$j]]; } } } return $array; } ``` ## 二分法 O(log2n) ``` function erfen($array,$a){ if(count($array) <= 1){ return $array; } $min = 0; $max = count($array)-1; while(true){ if($min<=$max){ $mid = floor(($min+$max)/2); if($array[$mid]==$a){ echo 'find';break; }elseif($array[$mid]>$a){ $max = $mid-1; }elseif($array[$mid] < $a){ $min = $mid+1; } }else{ echo 'no find';break; } } } ``` ## 快速排序O(nlogn) ``` function quickSort($arr){ if(count($arr)>1){ $count = count($arr); $mid = $arr[0]; $low = []; $hight = []; for($i=1;$i<$count;$i++){ if($arr[$i] > $mid){ $hight[] = $arr[$i]; }else{ $low[] = $arr[$i]; } } $low = quickSort($low); $hight = quickSort($hight); $end = array_merge($low,[$mid],$hight); return $end; }else{ return $arr; } } ``` ## 插入排序O(n2) ``` function sort_insert($array ){ if(count($array) <=1){ return $array; } $count = count($array); for($i=1;$i<$count;$i++){ for($j=0;$j<$count-1;$j++){ if($array[$i] > $array[$j]){ list($array[$j],$array[$i]) = [$array[$i],$array[$j]]; } } } return $array; } ``` ## 选择排序O(n2) ``` function selectSort($arr) { $len=count($arr); for($i=0; $i<$len-1; $i++) {//双重循环完成，外层控制轮数，内层控制比较次数 $p = $i;//先假设最小的值的位置 for($j=$i+1; $j<$len; $j++) { if($arr[$p] > $arr[$j]) {//$arr[$p] 是当前已知的最小值 $p = $j;//比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。 } } //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，则位置互换即可。 if($p != $i) { $tmp = $arr[$p];//3 $arr[$p] = $arr[$i];//4 $arr[$i] = $tmp; } } //返回最终结果 return $arr; } ``` ## 小牛 ``` 有一母牛，到4岁可生育，每年一头，所生均是一样的母牛， 到15岁绝育，不再能生，20岁死亡，问n年后有多少头牛。 function niu($year){ static $num = 1; for($i=1;$i<=$year;$i++){ if($i>=4 && $i<15){ $num++; niu($year-$i); } if($i==20){ $num--; } } return $num; } ``` ## 猴子大王，约瑟夫环 ``` function mk($n ,$m){ $arr = range(1,$n); $i=1; while(count($arr)>1){ if($i % $m != 0){ array_push($arr,$arr[$i-1]); } unset($arr[$i-1]); $i++; } return $arr[$i-1]; } ``` ## 买股票收益 ``` //[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入， //在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 // 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格； 同时，你不能在买入前卖出股票。 function gupiao($arrPrice) { $len = count($arrPrice); if($len <2){ return '不符合'; } $min = $arrPrice[0]; $maxProfit = 0; for($i=1;$i<$len;$i++){ $profit = $arrPrice[$i]-$min; $maxProfit = $maxProfit< $profit ? $profit : $maxProfit; if($min>$arrPrice[$i]){ $min = $arrPrice[$i]; } } return $maxProfit; } ``` ## 求两文件相对路径 ``` function test($apth,$bpth){ //拆分成数组 $a = explode('/', $apth); $b = explode('/', $bpth); //将两个数组的索引重置 $c = array_values(array_diff($a, $b));//[c,d,e.php] $d = array_values(array_diff($b, $a));//[12,34,c.php] //去除掉a路径的文件名 array_pop($c); //将a路径中的目录名替换为.. foreach ($c as &$v) $v = '..'; return implode("/",array_merge($c,$d)); } $a = '/a/b/c/d/e.php'; $b = '/a/b/12/34/c.php'; //var_dump(test($a,$b));die; ``` ## 递归目录 ``` function file_list($path){  if ($handle=opendir($path)) {   while (false!== ($file=readdir($handle))) {   if ($file!="."&&$file!="..") {   if (is_dir($path."/".$file)) {  echo $path.": ".$file."";//去掉此行显示的是所有的非目录文件                      file_list($path."/".$file);                  } else {   echo $path.": ".$file."";                 }             }         }     } } ``` ## 给出一个字符串，返回里面连续字母的个数，比如：abbcddde,返回 1a2b1c3de; ``` function strNum($str){ $endStr = ''; $wordArr = str_split($str); $num = count($wordArr); $key = 0; for($i=0;$i<$num;$i++){ $word = $wordArr[$i]; if($word == $wordArr[$i+1]){ continue; }else{ $endStr .= ($i-$key+1).$word; $key = $i+1; } } return $endStr; } ```