面试中经常被问到会什么算法,这里整合一些常见的算法及它们的实现原理.下面的例子都是经过测试可用的,如果有什么问题请告知!!
本人小白,如果有更好的实现方式,敬请赐教,感激不尽!!!!
冒泡排序,快速排序,选择排序,二分法查找,快速查找
/**
* 冒泡排序
* 相邻2数比较,小的在前,大的在后
* 数组有几个元素,就要比较几轮 $i
* 每轮需要比较的次数为,数组元素个数-已比较的次数 $j
* @param array$array 要操作的数组* @return array$array 返回的数组*/function bubbleSort($array)
{$cnt =count($array);for($i = 0;$i <$cnt ;$i++){for($j = 0 ;$j < ($cnt-$i-1) ;$j++){if($array[$j] >$array[$j+1]){$temp =$array[$j];$array[$j] =$array[$j+1];$array[$j+1] =$temp;
}
}
}return$array;
}
/**
* 快速排序
* 递归实现
* 获取数组第一个数,循环使后面的数与其比较,
* 比其小的放在一个数组中,比其大的放在一个数组中
* 将2个数组递归调用,直到最终数组元素小于等于1时,没有可以比较的元素
* 通过array_merge函数,将比较的数组按大小顺序合并然后一层一层的return出去,最终实现从小到大排序
* @param array $array 要操作的数组
* @return array $array 返回的数组*/functionquickSort($array)
{if(count($array) <= 1 )return$array;$key=$array[0];$left_arr=array();$right_arr=array();for($i=1;$i<count($array);$i++){if($array[$i] <=$key){$left_arr[] =$array[$i];
}else{$right_arr[] =$array[$i];
}
}$left_arr= quickSort($left_arr);$right_arr= quickSort($right_arr);returnarray_merge($left_arr,array($key),$right_arr);
}
/**
* 选择排序
* 2层循环
* 第一层逐个获取数组的值 $array[$i]
* 第二次遍历整个数组与$array[$i]比较($j=$i+1已经比较的,不再比较,减少比较次数)
* 如果比$array[$i]小,就交换位置
* 这样一轮下来就可以得到数组中最小值
* 以此内推整个外层循环下来就数组从小到大排序了
* @param array $array 要比较的数组
* @return array $array 从小到大排序后的数组*/functionselectSort($array){$cnt=count($array);for($i=0;$i<$cnt;$i++){for($j=($i+1);$j<$cnt;$j++){if($array[$i]>$array[$j]){$tmp=$array[$i];$array[$i] =$array[$j];$array[$j] =$tmp;
}
}
}return$array;
}
/**
* 二分法查找一个值在数组中的位置
* @param array $array 操作的数组
* @param void $val 要查找的值
* @return int $mid 返回要查找的值在数组中的索引,如果不存在返回-1*/functionbinarySearch($array,$val)
{$cnt=count($array);$low= 0;$high=$cnt- 1;while($low<=$high){$mid=intval(($low+$high)/2);if($array[$mid] ==$val){return$mid;
}if($array[$mid]<$val){$low=$mid+ 1;
}if($array[$mid]>$val){$high=$mid- 1;
}
}return-1;
}
/**
* 顺序查找(最简单,效率低下)
* 通过循环数组查找要的值
* @param array $array 要操作的数组
* @param void $val 要查找的值
* @return int 如果存在,返回该值在数组中的索引,否则返回-1*/functionseqSch($array,$val)
{for($i=0;$i<count($array);$i++){if($array[$i] ==$val)
break;
}if($i<count($array)){return$i;
}else{return-1;
}
}