最近突然迷恋上算法 了。温故而知新,这些简单而基础的东西是学习算法 的基石,所以又必要再次练习下。以下为纪念版,有错误的地方请包涵哈,也许将某个稳定的排序写成了不稳定的了。 呵呵!!
$arr = array (35 ,66 ,2 ,15 ,6 ,81 ,6 ,9 ,0 ,-2 ,9 );
function heapSort (&$arr ) {
initHeap($arr , 0 , count($arr ) - 1 );
for ($end = count($arr ) - 1 ; $end > 0 ; $end --) {
$temp = $arr [0 ];
$arr [0 ] = $arr [$end ];
$arr [$end ] = $temp ;
ajustNodes($arr , 0 , $end - 1 );
}
}
function initHeap (&$arr ) {
$len = count($arr );
for ($start = floor($len / 2 ) - 1 ; $start >= 0 ; $start --) {
ajustNodes($arr , $start , $len - 1 );
}
}
function ajustNodes (&$arr , $start , $end ) {
$maxInx = $start ;
$len = $end + 1 ;
$leftChildInx = ($start + 1 ) * 2 - 1 ;
$rightChildInx = ($start + 1 ) * 2 ;
if ($leftChildInx + 1 <= $len ) {
if ($arr [$maxInx ] < $arr [$leftChildInx ]) {
$maxInx = $leftChildInx ;
}
}
if ($rightChildInx + 1 <= $len ) {
if ($arr [$maxInx ] < $arr [$rightChildInx ]) {
$maxInx = $rightChildInx ;
}
}
if ($start != $maxInx ) {
$temp = $arr [$start ];
$arr [$start ] = $arr [$maxInx ];
$arr [$maxInx ] = $temp ;
if (($maxInx + 1 ) * 2 <= $len ) {
ajustNodes($arr , $maxInx , $end );
}
}
}
$arr = array (35 ,66 ,2 ,15 ,6 ,81 ,6 ,9 );
heapSort($arr );
print_r($arr );
function count_sort ($ary ) {
$tmp = array ();
for ($i = 0 ;$i < count($ary );$i ++) {
if ($max < $ary [$i ]) {
$max = $ary [$i ];
}
}
for ($i = 0 ;$i < $max ;$i ++) {
$tmp [$i ] = 0 ;
}
for ($i = 0 ;$i < count($ary );$i ++) {
$tmp [$ary [$i ]]++;
}
for ($i = 1 ; $i < count($tmp ); $i ++) {
$tmp [$i ] += $tmp [$i -1 ];
}
for ($i = 0 ; $i < count($ary ); $i ++) {
$tmp_ary [$tmp [$ary [$i ]]] = $ary [$i ];
$tmp [$ary [$i ]]--;
}
for ($i = 0 ; $i < count($tmp_ary ); $i ++) {
$ret [] = $tmp_ary [$i ];
}
return $ret ;
}
$arr = array (35 ,66 ,2 ,15 ,6 ,81 ,6 ,44 );
print_r(count_sort($arr ));
function quick_sort ($ary ) {
if (count($ary ) > 1 ) {
$left = array ();
$right = array ();
$pivot = $ary [0 ];
for ($i = 1 ;$i < count($ary );$i ++) {
if ($ary [$i ] >= $pivot ) $right [] = $ary [$i ];
else $left [] = $ary [$i ];
}
$left = quick_sort($left );
$right = quick_sort($right );
return array_merge($left ,array ($pivot ),$right );
} else {
return $ary ;
}
}
$arr = array (35 ,66 ,2 ,15 ,6 ,81 ,6 ,9 );
$sort_ary = quick_sort($ary );
print_r($sort_ary );
function partition (&$ary ,$low ,$high ) {
$tmp = $ary [$low ];
while ($low < $high ) {
while ($low < $high && $ary [$high ] >= $tmp ) {
$high --;
}
$ary [$low ] = $ary [$high ];
while ($low < $high && $ary [$low ] <= $tmp ) {
$low ++;
}
$ary [$high ] = $ary [$low ];
}
$ary [$low ] = $tmp ;
return $low ;
}
function quick_sort2 (&$ary ,$low ,$high ) {
if ($low < $high ) {
$p = partition($ary ,$low ,$high );
quick_sort($ary ,$low ,$p - 1 );
quick_sort($ary ,$p +1 ,$high );
}
return $ary ;
}
$arr = array (35 ,66 ,2 ,15 ,6 ,81 ,6 ,9 );
$sort_ary = quick_sort2($ary ,0 ,count($ary ));
print_r($sort_ary );
function cr_sort1 ($ary ) {
for ($i = 1 ;$i < count($ary );$i ++) {
$tmp = $ary [$i ];
$j = $i - 1 ;
while ($j >=0 && $ary [$j ] > $tmp ) {
$ary [$j + 1 ] = $ary [$j ];
$j --;
}
$ary [$j +1 ] = $tmp ;
}
return $ary ;
}
function cr_sort2 ($ary ) {
for ($i =1 ;$i < count($ary );$i ++) {
$tmp = $ary [$i ];
$j = $i ;
while ($j >= 0 && $tmp < $ary [$j -1 ]) {
$ary [$j ] = $ary [$j -1 ];
$j --;
}
$ary [$j ] = $tmp ;
}
return $ary ;
}
function cr_sort3 ($ary ) {
for ($i = 1 ;$i < count($ary );$i ++) {
$tmp = $ary [$i ];
$j = $i - 1 ;
$low = 0 ;
$high = $i - 1 ;
while ($low <= $high ) {
$mid = floor(($low + $high ) / 2 );
if ($tmp > $ary [$mid ]) $low = $mid + 1 ;
else $high = $mid - 1 ;
}
while ($j >= $low ) {
$ary [$j + 1 ] = $ary [$j ];
$j --;
}
$ary [$low ] = $tmp ;
}
return $ary ;
}
function shell_sort ($ary ) {
$d = count($ary );
while ($d > 1 ) {
$d = intval($d / 2 );
for ($i = $d ;$i < count($ary );$i +=$d ) {
$tmp = $ary [$i ];
$j = $i - $d ;
while ($j >= 0 && $ary [$j ] > $tmp ) {
$ary [$j + $d ] = $ary [$j ];
$j -= $d ;
}
$ary [$j +$d ] = $tmp ;
}
}
return $ary ;
}
function xz_sort (&$ary ) {
for ($i = 0 ;$i < count($ary );$i ++) {
$tmp = $ary [$i ];
for ($j = $i +1 ;$j < count($ary );$j ++) {
if ($ary [$i ] > $ary [$j ]) {
$sit = $j ;
$ary [$i ] = $ary [$j ];
}
}
if ($tmp != $ary [$i ]) {
$ary [$sit ] = $tmp ;
}
}
return $ary ;
}
$ary = array (23 ,-2 ,9 ,0 ,89 ,100 ,-23 );
$ary = cr_sort1($ary );
print_r($ary );
function mp_sort2 (&$ary ) {
for ($i = 0 ;$i < count($ary );$i ++) {
for ($j = 0 ;$j < count($ary ) - $i - 1 ;$j ++) {
if ($ary [$j ] > $ary [$j +1 ]) {
$tmp = $ary [$j ];
$ary [$j ] = $ary [$j +1 ];
$ary [$j +1 ] = $tmp ;
}
}
}
return $ary ;
}
function mp_sort (&$ary ) {
for ($i = 0 ;$i < count($ary );$i ++) {
for ($j = count($ary )-2 ;$j >= $i ;$j --) {
if ($ary [$j ] > $ary [$j +1 ]) {
$tmp = $ary [$j ];
$ary [$j ] = $ary [$j +1 ];
$ary [$j +1 ] = $tmp ;
}
}
}
return $ary ;
}
function div_search ($ary ,$key ) {
$low = 0 ;
$high = count($ary ) - 1 ;
$i = 0 ;
while ($low <= $high ) {
$mid = floor(($high +$low )/2 );
if ($key == $ary [$mid ]) return $key ;
elseif ($key < $ary [$mid ]) $high = $mid -1 ;
else $low = $mid + 1 ;
}
}
function re_div_search ($ary ,$key ,$low ,$high ) {
$mid = floor(($high +$low )/2 );
if ($key == $ary [$mid ]) return $key ;
elseif ($key < $ary [$mid ]) return re_div_search($ary ,$key ,$low ,$mid -1 );
else return re_div_search($ary ,$key ,$mid + 1 ,$high );
}
function find_str ($str ,$substr ) {
$i = 0 ;
$j =0 ;
while ($i <strlen($str ) && $j <strlen($substr )) {
if ($str [$i ]==$substr [$j ]) {
$i ++;
$j ++;
} else {
$i = $i - $j +1 ;
$j = 0 ;
}
}
if ($j == strlen($substr )) return true ;
return false ;
}
$str = 'XXXhello world' ;
$substr = 'ld' ;
echo find_str($str ,$substr );
exit ;
function findN ($n ) {
if ($n <= 2 ) return 1 ;
return findN($n -2 )+findN($n -1 );
}
function findN1 ($n ) {
$arr = array (1 ,1 );
if ($arr <= 2 ) return $arr ;
for ($i = 2 ;$i < $n ;$i ++) {
$arr [] = $arr [$i -1 ] + $arr [$i -2 ] ;
}
return implode(',' ,$arr );
}
print_r(findN1(7 ));exit ;
for ($i = 1 ;$i <=20 ;$i ++) {
echo findN($i );
echo '<br>' ;
}
exit ;