/**
* Created by PhpStorm.
* User: qishou
* Date: 15-8-2
* Time: 上午9:12
*/
header("content-type:text/html;charset=utf-8");
$arr=array(3,5,8,4,9,6,1,7,2);
echoimplode(" ",$arr)."
";
//---------------------------------------
// 常用排序算法
//---------------------------------------
//冒泡排序
functionBubbleSort($arr){
$length=count($arr);
if($length<=1){
return$arr;
}
for($i=0;$i<$length;$i++){
for($j=$length-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'冒泡排序：'
echoimplode(' ',BubbleSort($arr))."
";
//快速排序
functionQSort($arr){
$length=count($arr);
if($length<=1){
return$arr;
}
$pivot=$arr[0];//枢轴
$left_arr=array();
$right_arr=array();
for($i=1;$i<$length;$i++){//注意$i从1开始0是枢轴
if($arr[$i]<=$pivot){
$left_arr[] =$arr[$i];
}else{
$right_arr[] =$arr[$i];
}
}
$left_arr= QSort($left_arr);//递归排序左半部分
$right_arr= QSort($right_arr);//递归排序右半部份
returnarray_merge($left_arr,array($pivot),$right_arr);//合并左半部分、枢轴、右半部分
}
echo"快速排序：";
echoimplode(' ',QSort($arr))."
";
//选择排序(不稳定)
functionSelectSort($arr){
$length=count($arr);
if($length<=1){
return$arr;
}
for($i=0;$i<$length;$i++){
$min=$i;
for($j=$i+1;$j<$length;$j++){
if($arr[$j]<$arr[$min]){
$min=$j;
}
}
if($i!=$min){
$tmp=$arr[$i];
$arr[$i] =$arr[$min];
$arr[$min] =$tmp;
}
}
return$arr;
}
echo"选择排序：";
echoimplode(' ',SelectSort($arr))."
";
//插入排序
functionInsertSort($arr){
$length=count($arr);
if($length<=1){
return$arr;
}
for($i=1;$i<$length;$i++){
$x=$arr[$i];
$j=$i-1;
while($x<$arr[$j] j="">=0){
$arr[$j+1] =$arr[$j];
$j--;
}
$arr[$j+1] =$x;
}
return$arr;
}
echo'插入排序：'
echoimplode(' ',InsertSort($arr))."
";
//---------------------------------------
// 常用查找算法
//---------------------------------------
//二分查找
functionbinary_search($arr,$low,$high,$key){
while($low<=$high){
$mid=intval(($low+$high)/2);
if($key==$arr[$mid]){
return$mid+1;
}elseif($key<$arr[$mid]){
$high=$mid-1;
}elseif($key>$arr[$mid]){
$low=$mid+1;
}
}
return-1;
}
$key= 6;
echo"二分查找{$key}的位置：";
echobinary_search(QSort($arr),0,8,$key);
//顺序查找
functionSqSearch($arr,$key){
$length=count($arr);
for($i=0;$i<$length;$i++){
if($key==$arr[$i]){
return$i+1;
}
}
return-1;
}
$key= 8;
echo"
顺序常规查找{$key}的位置：";
echoSqSearch($arr,$key);
//---------------------------------------
// 常用数据结构
//---------------------------------------
//线性表的删除(数组实现)
functiondelete_array_element($arr,$pos){
$length=count($arr);
if($pos<1 pos="">$length){
return"删除位置出错!";
}
for($i=$pos-1;$i<$length-1;$i++){
$arr[$i] =$arr[$i+1];
}
array_pop($arr);
return$arr;
}
$pos= 3;
echo"
除第{$pos}位置上的元素后：";
echoimplode(' ',delete_array_element($arr,$pos))."
";
/**
* Class Node
* PHP模拟链表的基本操作
*/
classNode{
public$data=''
public$next= null;
}
//初始化
functioninit($linkList){
$linkList->data = 0;//用来记录链表长度
$linkList->next = null;
}
//头插法创建链表
functioncreateHead(&$linkList,$length){
for($i=0;$i<$length;$i++){
$newNode=newNode();
$newNode->data =$i;
$newNode->next =$linkList->next;//因为PHP中对象本身就是引用所以不用再可用“&”
$linkList->next =$newNode;
$linkList->data++;
}
}
//尾插法创建链表
functioncreateTail(&$linkList,$length){
$r=$linkList;
for($i=0;$i<$length;$i++){
$newNode=newNode();
$newNode->data =$i;
$newNode->next =$r->next;
$r->next =$newNode;
$r=$newNode;
$linkList->data++;
}
}
//在指定位置插入指定元素
functioninsert($linkList,$pos,$elem){
if($pos<1 pos="">$linkList->data+1){
echo"插入位置错误！";
}
$p=$linkList;
for($i=1;$i<$pos;$i++){
$p=$p->next;
}
$newNode=newNode();
$newNode->data =$elem;
$newNode->next =$p->next;
$p->next =$newNode;
}
//删除指定位置的元素
functiondelete($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--;
}
//输出链表数据
functionshow($linkList){
$p=$linkList->next;
while($p!=null){
echo$p->data." ";
$p=$p->next;
}
echo'
'
}
$linkList=newNode();
init($linkList);//初始化
createTail($linkList,10);//尾插法创建链表
show($linkList);//打印出链表
insert($linkList,3,'a');//插入
show($linkList);
delete($linkList,3);//删除
show($linkList);
/**
* Class Stack
* 用PHP模拟顺序栈的基本操作
*/
classStack{
//用默认值直接初始化栈了，也可用构造方法初始化栈
private$top= -1;
private$maxSize= 5;
private$stack=array();
//入栈
publicfunctionpush($elem){
if($this->top >=$this->maxSize-1){
echo"栈已满！
";
return;
}
$this->top++;
$this->stack[$this->top] =$elem;
}
//出栈
publicfunctionpop(){
if($this->top == -1){
echo"栈是空的！";
return;
}
$elem=$this->stack[$this->top];
unset($this->stack[$this->top]);
$this->top--;
return$elem;
}
//打印栈
publicfunctionshow(){
for($i=$this->top;$i>=0;$i--){
echo$this->stack[$i]." ";
}
echo"
";
}
}
$stack=newStack();
$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实现双向队列
*/
classDeque{
private$queue=array();
publicfunctionaddFirst($item){//头入队
array_unshift($this->queue,$item);
}
publicfunctionaddLast($item){//尾入队
array_push($this->queue,$item);
}
publicfunctionremoveFirst(){//头出队
array_shift($this->queue);
}
publicfunctionremoveLast(){//尾出队
array_pop($this->queue);
}
publicfunctionshow(){//打印
foreach($this->queueas$item){
echo$item." ";
}
echo"
";
}
}
$deque=newDeque();
$deque->addFirst(2);
$deque->addLast(3);
$deque->addLast(4);
$deque->addFirst(5);
$deque->show();
//PHP解决约瑟夫环问题
//方法一
functionjoseph_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];
}
//方法二
functionjoseph_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)."
";
