[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; } ```