PHP常用アルゴリズムとデータ構造を記録する

php 
header('content-type:text/html;charset=utf-8');
$arr = array(3,2,5,8,23,54,44,6,22,9);
echo implode(' ', $arr)."
";
/*
      
 */
//    
function BubbleSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    for($i = 0;$i < $len;$i++){
        for($j = $len - 1;$j > $i;$j--){
            if($arr[$j] < $arr[$j-1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $tmp;
            }
        }
    }
    return $arr;
}
echo "
    ：
";
var_dump(BubbleSort($arr));

//    
function QuickSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $pt = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for($i = 1;$i < $len;$i++){
        if($arr[$i] <= $pt){
            $left_arr[] = $arr[$i];
        }else{
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = QuickSort($left_arr);
    $right_arr = QuickSort($right_arr);
    return array_merge($left_arr,[$arr[0]],$right_arr);
}
echo "
    ：
";
var_dump(QuickSort($arr));

//    （   ）
function SelectSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    for($i = 0;$i < $len;$i++){
        $min = $i;
        for($j = $i + 1;$j<$len;$j++){
            if($arr[$j] < $arr[$min]){
                $min = $j;
            }
        }
        if($i != $min){
            $tmp = $arr[$i];
            $arr[$i] = $arr[$min];
            $arr[$min] = $tmp;
        }
    }
    return $arr;
}
echo "
    ：
";
var_dump(SelectSort($arr));

//    
function InsertSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    for($i = 1;$i < $len;$i++){
        $x = $arr[$i];
        $y = $i - 1;
        while($x < $arr[$y] && $y >= 0){
            $arr[$y + 1] = $arr[$y];
            $y--;
        }
        $arr[$y+1] = $x;
    }
    return $arr;
}
echo "
    ：
";
var_dump(InsertSort($arr));

/**
 *       
 */
//    (  )
$arr = BubbleSort($arr);
function BinarySearch($arr,$low,$high,$key){
    if($low <= $high){
        if(($low + $high) % 2 == 0){
            $mid = ($low + $high) / 2;
        } else {
            $mid = floor(($low + $high) / 2);
        }

        if($arr[$mid] == $key){
            return $mid;
        }

        if($arr[$mid] > $key){
            return BinarySearch($arr, $low, $mid - 1, $key);
        }

        if($arr[$mid] < $key){
            return BinarySearch($arr, $mid + 1, $high, $key);
        }
    }else{
        return null;
    }
}
$key = 6;
echo "
    （  ）{$key}   ：
";
echo BinarySearch($arr,0,count($arr),$key);

//    (   )
function BinarySearch1($arr,$search){
    $low = 0;
    $high = count($arr) - 1;

    while($low <= $high){
        if(($low + $high) % 2 == 0){
            $mid = ($low + $high) / 2;
        }else{
            $mid = floor(($low +$high) / 2);
        }

        $guess = $arr[$mid];

        if($guess == $search){
            return $mid;
        }

        if($guess > $search){
            $high = $mid - 1;
        }

        if($guess < $search){
            $low = $mid + 1;
        }
    }

    return null;
}
$key = 22;
echo "
    （   ）{$key}   ：
";
echo BinarySearch1($arr,$key);

//    
function OrderSearch($arr,$key){
    $len = count($arr);
    for($i = 0;$i < $len;$i++){
        if($key == $arr[$i]){
            return $i;
        }
    }
    return -1;
}
$key = 44;
echo "
    {$key}   ：
";
echo OrderSearch($arr,$key);

/**
 *       
 */
//      （    ）
function DeleteArrElem($arr,$pos){
    $len = count($arr);
    if($pos < 1 || $pos > $len){
        return '      ！';
    }
    for($i = $pos - 1;$i < $len - 1;$i++){
        $arr[$i] = $arr[$i+1];
    }
    array_pop($arr);
    return $arr;
}
$pos = 3;
echo "
   {$pos}       ：
";
var_dump(DeleteArrElem($arr,$pos));
echo "
";

/**
 * Class Node
 * PHP         
 */
class Node{
  public $data = '';
  public $next = null;
}
//   
function init($linkList){
  $linkList->data = 0; //        
  $linkList->next = null;
}
//       
function createHead(&$linkList,$length){
  for($i=0;$i<$length;$i++){
    $newNode = new Node();
    $newNode->data = $i;
    $newNode->next = $linkList->next;//  PHP                “&”
    $linkList->next = $newNode;
    $linkList->data++;
  }
}
//       
function createTail(&$linkList,$length){
  $r = $linkList;
  for($i=0;$i<$length;$i++){
    $newNode = new Node();
    $newNode->data = $i;
    $newNode->next = $r->next;
    $r->next = $newNode;
    $r = $newNode;
    $linkList->data++;
  }
}
//           
function insert($linkList,$pos,$elem){
  if($pos<1 && $pos>$linkList->data+1){
    echo "      ！";
  }
  $p = $linkList;
  for($i=1;$i<$pos;$i++){
    $p = $p->next;
  }
  $newNode = new Node();
  $newNode->data = $elem;
  $newNode->next = $p->next;
  $p->next = $newNode;
}
//         
function delete($linkList,$pos){
  if($pos<1 && $pos>$linkList->data+1){
    echo "     ！";
  }
  $p = $linkList;
  for($i=1;$i<$pos;$i++){
    $p = $p->next;
  }
  $q = $p->next;
  $p->next = $q->next;
  unset($q);
  $linkList->data--;
}
//      
function show($linkList){
  $p = $linkList->next;
  while($p!=null){
    echo $p->data." ";
    $p = $p->next;
  }
  echo '
';
}
 
$linkList = new Node();
init($linkList);//   
createTail($linkList,10);//       
show($linkList);//     
insert($linkList,3,'a');//  
show($linkList);
delete($linkList,3);//  
show($linkList);
 
/**
 * Class Stack
 *  PHP          
 */
class Stack{
  //           ，           
  private $top = -1;
  private $maxSize = 5;
  private $stack = array();
 
  //  
  public function push($elem){
    if($this->top >= $this->maxSize-1){
      echo "   ！
";
      return;
    }
    $this->top++;
    $this->stack[$this->top] = $elem;
  }
  //  
  public function pop(){
    if($this->top == -1){
      echo "    ！";
      return ;
    }
    $elem = $this->stack[$this->top];
    unset($this->stack[$this->top]);
    $this->top--;
    return $elem;
  }
  //   
  public function show(){
    for($i=$this->top;$i>=0;$i--){
      echo $this->stack[$i]." ";
    }
    echo "
";
  }
}
 
$stack = new Stack();
$stack->push(3);
$stack->push(5);
$stack->push(8);
$stack->push(7);
$stack->push(9);
$stack->push(2);
$stack->show();
$stack->pop();
$stack->pop();
$stack->pop();
$stack->show();
 
/**
 * Class Deque
 *   PHP      
 */
class Deque{
  private $queue = array();
  public function addFirst($item){//   
    array_unshift($this->queue,$item);
  }
  public function addLast($item){//   
    array_push($this->queue,$item);
  }
  public function removeFirst(){//   
    array_shift($this->queue);
  }
  public function removeLast(){//   
    array_pop($this->queue);
  }
  public function show(){//  
    foreach($this->queue as $item){
      echo $item." ";
    }
    echo "
";
  }
}
$deque = new Deque();
$deque->addFirst(2);
$deque->addLast(3);
$deque->addLast(4);
$deque->addFirst(5);
$deque->show();
 
//PHP        
//   
function joseph_ring($n,$m){
  $arr = range(1,$n);
  $i = 0;
  while(count($arr)>1){
    $i=$i+1;
    $head = array_shift($arr);
    if($i%$m != 0){ //           
      array_push($arr,$head);
    }
  }
  return $arr[0];
}
//   
function joseph_ring2($n,$m){
  $r = 0;
  for($i=2;$i<=$n;$i++){
    $r = ($r+$m)%$i;
  }
  return $r + 1;
}
echo joseph_ring(60,5)."
";
echo joseph_ring2(60,5)."
";