Home >Backend Development >PHP Tutorial >php data structures and algorithms
<?php
class Test implements Iterator{ private $item = array('id'=>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,'<br/>';
}?>
<?php
class Deque{ private $queue=array(); public function addFirst($item){ return array_unshift($this->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);
}
}?>
<?php
// 冒泡排序
function bubble_sort(&$arr){ for ($i=0,$len=count($arr); $i < $len; $i++) { for ($j=1; $j < $len-$i; $j++) { if ($arr[$j-1] > $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);?>
<?php
//快速排序
function partition(&$arr,$low,$high){
$pivotkey = $arr[$low]; while($low<$high){ while($low < $high && $arr[$high] >= $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);
}
}?>
This algorithm is implemented through divide-and-conquer recursion. Its efficiency depends largely on the selection of reference elements. You can choose the middle element of the array, or you can get three elements randomly, and then Select the middle element (median of three numbers).
Another point is that when we are dividing, if the length of the divided subsequence is very small (less than 5 to 20), the efficiency of recursive sorting is usually not as fast as insertion sorting or Hill sorting. . Therefore, you can judge the length of the array. If it is less than 10, use insertion sort directly instead of calling this quick sort recursively.
This is the famous Joseph Ring problem
<?php
// 方案一，使用php来模拟这个过程
function king($n,$m){
$mokey = range(1, $n);
$i = 0; while (count($mokey) >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));?>
<?php//二维数组排序，$arr是数据，$keys是排序的健值，$order是排序规则，1是降序，0是升序function array_sort($arr,$keys,$order=0){ if(!is_array($arr)){ return false;
}
$keysvalue=array(); foreach($arr as $key => $val){
$keysvalue[$key] = $val[$keys];
} if($order == 0){
asort($keysvalue);
}else{
arsort($keysvalue);
}
reset($keysvalue); foreach($keysvalue as $key => $vals){
$keysort[$key] = $key;
}
$new_array=array(); foreach($keysort as $key=> $val){
$new_array[$key]=$arr[$val];
} return$new_array;
} //测试
$person=array( array('id'=>2,'name'=>'zhangsan','age'=>23), array('id'=>5,'name'=>'lisi','age'=>28), array('id'=>3,'name'=>'apple','age'=>17)
);
$result = array_sort($person,'name',1);
print_r($result);?>
4
7/15
75%. Each mouse has two directions of movement: clockwise and counterclockwise. There are 8 types of movement conditions for 3 mice. Only when all 3 mice are moving clockwise or counterclockwise , they will not meet, and the remaining 6 situations will meet, so the probability of meeting is 6/8=75%.
<?php
/**
* 顺序查找
* @param array $arr 数组
* @param $k 要查找的元素
* @return mixed 成功返回数组下标，失败返回-1
*/
function seq_sch($arr,$k){ for ($i=0,$n = count($arr); $i < $n; $i++) { if ($arr[$i] == $k) { break;
}
} if($i < $n){ return $i;
}else{ return -1;
}
} /**
* 二分查找，要求数组已经排好顺序
* @param array $array 数组
* @param int $low 数组起始元素下标
* @param int $high 数组末尾元素下标
* @param $k 要查找的元素
* @return mixed 成功时返回数组下标，失败返回-1
*/
function bin_sch($array,$low,$high,$k){ if ($low <= $high) {
$mid = intval(($low + $high) / 2); if ($array[$mid] == $k) { return $mid;
} elseif ($k < $array[$mid]) { return bin_sch($array,$low,$mid - 1,$k);
} else{ return bin_sch($array,$mid + 1,$high,$k);
}
} return -1;
} // 测试：顺序查找
$arr1 = array(9,15,34,76,25,5,47,55); echo seq_sch($arr1,47);//结果为6
echo "<br />"; // 测试：二分查找
$arr2 = array(5,9,15,25,34,47,55,76); echo bin_sch($arr2,0,7,47);//结果为5?>
<?php
$card_num = 54;//牌数
function wash_card($card_num){
$cards = $tmp = array(); for($i = 0;$i < $card_num;$i++){
$tmp[$i] = $i;
} for($i = 0;$i < $card_num;$i++){
$index = rand(0,$card_num-$i-1);
$cards[$i] = $tmp[$index]; unset($tmp[$index]);
$tmp = array_values($tmp);
} return $cards;
} // 测试：
print_r(wash_card($card_num));?>
冒泡排序，快速排序，插入排序，选择排序。
The above is the detailed content of php data structures and algorithms. For more information, please follow other related articles on the PHP Chinese website!