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