2023年7月3日发(作者：)

PHP中的⼀些基本算法和数据结构（⼀）1.0：冒泡排序基本思想：对需要排序的数组从后往前（逆序）进⾏多遍的扫描，当发现相邻的两个数值的次序与排序要求的规则不⼀致时，就将这两个数值进⾏交换。这样⽐较⼩（⼤）的数值就将逐渐从后⾯向前⾯移动。1.1：快速排序基本思想：在数组中挑出⼀个元素（多为第⼀个）作为标尺，扫描⼀遍数组将⽐标尺⼩的元素排在标尺之前，将所有⽐标尺⼤的元素排在标尺之后，通过递归将各⼦序列分别划分为更⼩的序列直到所有的序列顺序⼀致。 $arr[$i]){//放⼊左边数组$left_array[] = $arr[$i];}else{//放⼊右边$right_array[] = $arr[$i];}}//再分别对 左边 和 右边的数组进⾏相同的排序处理⽅式//递归调⽤这个函数,并记录结果$left_array = quick_sort($left_array);$right_array = quick_sort($right_array);//合并左边 标尺 右边return array_merge($left_array, array($base_num), $right_array);}$arr = array(3,1,2);var_dump(quick_sort($arr));>

1.2：⼆分查找基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始⽐较，如果当前位置值等于x，则查找成功；若x⼩于当前位置值，则在数列的前半段中查找；若x⼤于当前位置值则在数列的后半段中继续查找，直到找到为⽌。（数据量⼤的时候使⽤）

1.3：顺序查找基本思想：从数组的第⼀个元素开始⼀个⼀个向下查找，如果有和⽬标⼀致的元素，查找成功；如果到最后⼀个元素仍没有⽬标元素，则查找失败。

1.4：遍历⽂件夹

1.5：写⼀个函数，尽可能⾼效的从⼀个标准url中取出⽂件的扩展名 string 'http' (length=4)//'host' => string '' (length=15)//'path' => string '/abc/de/' (length=14)//'query' => string 'id=1' (length=4)$file = basename($arr['path']);// basename函数返回路径中的⽂件名部分$ext = explode('.', $file);return $ext[count($ext)-1];}print(getExt('/abc/de/?id=1'));>.⽤多种⽅式获取url的后缀名？$url="localhost/user/?id=3";//第⼀种：pathinfo()函数$url1 = '/?id=1234&a=qwer';$array = pathinfo($url1);$extension = $array['extension'];$position = strpos($extension, '?');$result = $position === false ? $extension : substr($extension, 0, $position);echo $result."
";

//第⼆种:parse_url()函数$url2 = '/?id=1234&a=qwer';$array = parse_url($url2);$path = $array['path'];$result2 = substr($path, strpos($path, '.'));echo $result2;

1.6：实现中⽂字符串截取⽆乱码的⽅法可使⽤mb_substr,但是需要确保在中加载了php_，即确保“extension=php_”这⼀⾏存在并且没有被注释掉，否则会出现未定义函 数的问题。

1.7：数据结构和算法使对象可以像数组⼀样进⾏foreach循环，要求属性必须是私有。(Iterator模式的PHP5实现，写⼀类实现Iterator接⼝)（腾讯）1,'name'=>'php');public function rewind(){reset($this->item);}public function current(){return current($this->item);}public function key(){return key($this->item);}public function next(){return next($this->item);}public function valid(){return($this->current()!==false);}}//测试$t=new Test;foreach($t as $k=>$v){echo$k,'--->',$v,'
';}>

1.8：⽤PHP 实现⼀个双向队列（腾讯）queue,$item);}public function addLast($item){return array_push($this->queue,$item);}public function removeFirst(){return array_shift($this->queue);}public function removeLast(){return array_pop($this->queue);}}>

实战开始：：：1.10：冒泡排序对数组$arr=array(10,2,36,14,10,25,23,85,99,45);进⾏排序 $arr[$j]) {$temp = $arr[$j-1];$arr[$j-1] = $arr[$j];$arr[$j] = $temp;}}}}// 测试$arr = array(10,2,36,14,10,25,23,85,99,45);bubble_sort($arr);print_r($arr);>

1.11：写⼀种算法，并切进⾏优化（新浪）= $pivotkey){$high--;}$temp = $arr[$low];$arr[$low] = $arr[$high];$arr[$high] = $temp;while($low < $high && $arr[$low] <= $pivotkey){$low++;}$temp=$arr[$low];$arr[$low]=$arr[$high];$arr[$high]=$temp;}return$low;}function quick_sort(&$arr,$low,$high){if($low < $high){$pivot = partition($arr,$low,$high);quick_sort($arr,$low,$pivot-1);quick_sort($arr,$pivot+1,$high);}}>

1.12：⾯试题猴⼦算法：⼀群猴⼦排成⼀圈，按1，2，...，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后⾯再开始数，再数到第m只，在把它踢出去...，如此不停的进⾏下去，直到最后只剩下⼀只猴⼦为⽌，那只猴⼦就叫做⼤王。要求编程模拟此过程，输⼊m、n,输出最后那个⼤王的编号。（新浪）（⼩⽶）1) {$i += 1;$head = array_shift($mokey);//⼀个个出列最前⾯的猴⼦if ($i % $m !=0) {#如果不是m的倍数，则把猴⼦返回尾部，否则就抛掉，也就是出列array_push($mokey,$head);}// 剩下的最后⼀个就是⼤王了return $mokey[0];}}// 测试echo king(10,7);// ⽅案⼆，使⽤数学⽅法解决function josephus($n,$m){$r = 0;for ($i=2; $i <= $m ; $i++) {$r = ($r + $m) % $i;}return $r+1;}// 测试print_r(josephus(10,7));>

1.13：⼆维数组排序算法函数，能够具有通⽤性，可以调⽤php内置函数 $val){ $keysvalue[$key] = $val[$keys]; }print_r($keysvalue);//对数组按照指定字段排序并保持索引关系 if($order == 0){ asort($keysvalue); }else{ arsort($keysvalue); }print_r($keysvalue);

$new_array=array();//按照排好序的下标，重新组合原⼆维数组 foreach($keysvalue as $key => $val){ $new_array[$key] = $arr[$key]; } return $new_array;} //测试 $person=array( array('id'=>2,'name'=>'lhangsan','age'=>23), array('id'=>5,'name'=>'zisi','age'=>28), array('id'=>3,'name'=>'apple','age'=>17) ); $result = array_sort($person,'name',0); print_r($result);

>

1.14：顺序查找和⼆分查找（也叫做折半查找）算法，顺序查找必须考虑效率，对象可以是⼀个有序数组（⼩⽶）";// 测试：⼆分查找$arr2 = array(5,9,15,25,34,47,55,76);echo bin_sch($arr2,0,7,47);//结果为5>

1.15：洗牌算法