Algorithm analysis of PHP interview questions, PHP test question analysis

Algorithm analysis of PHP interview questions, PHP test question analysis_PHP tutorial

WBOY

Release： 2016-07-12 09:07:41

Original

858 people have browsed it

Algorithm analysis of PHP interview questions, PHP test question analysis

In interviews, we are often asked what algorithms we know. Here are some common algorithms and their implementation principles. The following examples They are all tested and available. If you have any questions, please let us know!!

I am a novice, if there is a better way to achieve it, please enlighten me, I will be grateful!!!!

Bubble sort, quick sort, selection sort, binary search, quick search

<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>

Copy after login

<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>

Copy after login

<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>

Copy after login

<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>

Copy after login

<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>

Copy after login