phpの一般的なアルゴリズム実装
9720 ワード
<?php
$arr = array(35,66,2,15,6,81,6,9,0,-2,9);
/* : （ ） ， ， 、 。
：http://www.cnblogs.com/zemliu/archive/2012/08/18/2645941.html
*/
function heapSort(&$arr) {
# ，
initHeap($arr, 0, count($arr) - 1);
//print_r($arr);exit;
# , ,
for($end = count($arr) - 1; $end > 0; $end--) { // ， ，
//
$temp = $arr[0];
$arr[0] = $arr[$end];
$arr[$end] = $temp;
ajustNodes($arr, 0, $end - 1);
}
}
# , , /2
function initHeap(&$arr) {
$len = count($arr);
for($start = floor($len / 2) - 1; $start >= 0; $start--) {
ajustNodes($arr, $start, $len - 1);
}
}
#
#@param $arr
#@param $start
#@param $end
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;
}
}
// ， 、 、 ， maxInx 。
#
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];
}
//print_r($tmp);
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];// : ， low
while($low < $high && $ary[$low] <= $tmp) {
$low++;
}
$ary[$high] = $ary[$low];// ， high , ，
// 。
}
$ary[$low] = $tmp;// ， low ， low ， ，
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;
}
//$ary[$i] = $flag;
}
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; // ，i ！
$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;
//$ary = array(100,1,10,10,2,8,890,4,-98,39,89,12,-2);
//$ary = mp_sort($ary);
//print_r($ary);