php面试常见算法题
二分法查找:
function twofunction ( $array , $low , $height , $k )
{
if ( is_array ( $array ) ) {
$mid = ( $low + $height ) / 2 ;
if ( $low <= $height ) {
if ( $array [ $mid ] == $k ) {
return $mid ;
} elseif ( $array [ $mid ] > $k ) {
return twofunction ( $array , $low , $mid - 1 , $k ) ;
} elseif ( $array [ $mid ] < $k ) {
return twofunction ( $array , $mid + 1 , $height , $k ) ;
} else {
return - 1 ;
}
} else {
return - 1 ;
}
}
}
顺序查找
function sort_function ( $arr , $num , $val )
{
for ( $i = 0 ; $i < $num ; $i ++ ) {
if ( $arr [ $i ] == $val ) {
break ;
}
}
if ( $i < $num ) {
return $i ;
} else {
return - 1 ;
}
}
二维数组排序
function arraySort ( $arr , $keys , $type )
{
$keysvalue = $new_array = array ( ) ;
foreach ( $arr as $k => $v ) {
$keysvalue [ $k ] = $v [ $keys ] ;
}
$type == 'asc' ? asort ( $keysvalue ) : arsort ( $keysvalue ) ;
reset ( $keysvalue ) ;
foreach ( $keysvalue as $k => $v ) {
$new_array [ $k ] = $arr [ $k ] ;
}
return $new_array ;
}
冒泡排序
function maopao ( $array )
{
$len = count ( $array ) ;
if ( $len <= 1 ) return $array ;
for ( $i = 0 ; $i < $len - 1 ; $i ++ ) {
for ( $j = 0 ; $j < $len - $i - 1 ; $j ++ ) {
if ( $array [ $j ] > $array [ $j + 1 ] ) {
$tem = $array [ $j ] ;
$array [ $j ] = $array [ $j + 1 ] ;
$array [ $j + 1 ] = $tem ;
}
}
}
return $array ;
}
快速排序
function quick_sort ( $array )
{
$len = count ( $array ) ;
if ( $len <= 1 ) return $array ;
$key = $array [ 0 ] ;
$array_left = array ( ) ;
$array_right = array ( ) ;
for ( $i = 1 ; $i < $len ; $i ++ ) {
if ( $key > $array [ $i ] ) {
array_push ( $array_left , $array [ $i ] ) ;
} else {
$array_right [ ] = $array [ $i ] ;
}
}
$array_left = quick_sort ( $array_left ) ;
$array_right = quick_sort ( $array_right ) ;
return array_merge ( $array_left , array ( $key ) , $array_right ) ;
}
选择排序
function select_sort ( $array )
{
if ( count ( $array ) <= 1 ) return $array ;
for ( $i = 0 ; $i < count ( $array ) - 1 ; $i ++ ) {
$min = $i ;
for ( $j = $i + 1 ; $j < count ( $array ) ; $j ++ ) {
if ( $array [ $min ] > $array [ $j ] ) {
$min = $j ;
}
}
if ( $min != $i ) {
$tmp = $array [ $min ] ;
$array [ $min ] = $array [ $i ] ;
$array [ $i ] = $tmp ;
}
}
return $array ;
}
插入排序
function insert_sort ( $array )
{
if ( count ( $array ) <= 1 ) return $array ;
for ( $i = 1 ; $i < count ( $array ) ; $i ++ ) {
$tmp = $array [ $i ] ;
for ( $j = $i - 1 ; $j >= 0 ; $j -- ) {
if ( $array [ $j ] > $tmp ) {
$array [ $j + 1 ] = $array [ $j ] ;
$array [ $j ] = $tmp ;
} else {
break ;
}
}
}
return $array ;
}