Home >Backend Development >PHP Tutorial >PHP implementation of classic algorithms, 300 classic examples of PHP programming, classic examples of PHP recursive algorithms, PHP classic interviews
Foreword
The following is a classic algorithm implemented through PHP, and the time consumption is calculated. The complexity of these algorithms can be compared by the time consumption.
CODE
<code><span>$arr</span> = []; <span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> < <span>5000</span>; <span>$i</span>++) { <span>$arr</span>[] = rand(<span>1</span>, <span>10000</span>); } <span>//1 插入排序</span><span><span>function</span><span>insertionSort</span><span>(<span>$arr</span>)</span> {</span><span>for</span> (<span>$i</span> = <span>1</span>; <span>$i</span> < count(<span>$arr</span>); <span>$i</span>++) { <span>$tmp</span> = <span>$arr</span>[<span>$i</span>]; <span>//设置监视哨</span><span>$key</span> = <span>$i</span> - <span>1</span>; <span>//设置开始查找的位置</span><span>while</span> (<span>$key</span> >= <span>0</span> && <span>$tmp</span> < <span>$arr</span>[<span>$key</span>]) { <span>// 监视哨的值比查找的值小 并且 没有到此次查询的第一个</span><span>$arr</span>[<span>$key</span> + <span>1</span>] = <span>$arr</span>[<span>$key</span>]; <span>//数组的值进行后移</span><span>$key</span>--; <span>//要查找的位置后移</span> } <span>if</span> ((<span>$key</span> + <span>1</span>) != <span>$i</span>) <span>//放置监视哨</span><span>$arr</span>[<span>$key</span> + <span>1</span>] = <span>$tmp</span>; } <span>return</span><span>$arr</span>; } <span>$insertion_start_time</span> = microtime(<span>true</span>); <span>$insertion_sort</span> = insertionSort(<span>$arr</span>); <span>$insertion_end_time</span> = microtime(<span>true</span>); <span>$insertion_need_time</span> = <span>$insertion_end_time</span> - <span>$insertion_start_time</span>; print_r(<span>"插入排序耗时:"</span> . <span>$insertion_need_time</span> . <span>"<br />"); <span>//2 冒泡排序</span><span><span>function</span><span>bubbleSort</span><span>(<span>$arr</span>)</span> {</span><span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> < count(<span>$arr</span>); <span>$i</span>++) { <span>for</span> (<span>$j</span> = <span>0</span>; <span>$j</span> < <span>$i</span> + <span>1</span>; <span>$j</span>++) { <span>if</span> (<span>$arr</span>[<span>$j</span>] < <span>$arr</span>[<span>$j</span> - <span>1</span>]) { <span>$temp</span> = <span>$arr</span>[<span>$j</span> - <span>1</span>]; <span>$arr</span>[<span>$j</span> - <span>1</span>] = <span>$arr</span>[<span>$j</span>]; <span>$arr</span>[<span>$j</span>] = <span>$temp</span>; } } } <span>return</span><span>$arr</span>; } <span>$bubble_start_time</span> = microtime(<span>true</span>); <span>$bubble_sort</span> = bubbleSort(<span>$arr</span>); <span>$bubble_end_time</span> = microtime(<span>true</span>); <span>$bubble_need_time</span> = <span>$bubble_end_time</span> - <span>$bubble_start_time</span>; print_r(<span>"冒泡排序耗时:"</span> . <span>$bubble_need_time</span> . <span>"<br />"); <span>//3 选择排序</span><span><span>function</span><span>selectionSort</span><span>(<span>$arr</span>)</span> {</span><span>$count</span> = count(<span>$arr</span>); <span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> < <span>$count</span> - <span>1</span>; <span>$i</span>++) { <span>//找到最小的值</span><span>$min</span> = <span>$i</span>; <span>for</span> (<span>$j</span> = <span>$i</span> + <span>1</span>; <span>$j</span> < <span>$count</span>; <span>$j</span>++) { <span>//由小到大排列</span><span>if</span> (<span>$arr</span>[<span>$min</span>] > <span>$arr</span>[<span>$j</span>]) { <span>//表明当前最小的还比当前的元素大</span><span>$min</span> = <span>$j</span>; <span>//赋值新的最小的</span> } } <span>/*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/</span><span>if</span> (<span>$min</span> != <span>$i</span>) { <span>$temp</span> = <span>$arr</span>[<span>$min</span>]; <span>$arr</span>[<span>$min</span>] = <span>$arr</span>[<span>$i</span>]; <span>$arr</span>[<span>$i</span>] = <span>$temp</span>; } } <span>return</span><span>$arr</span>; } <span>$selection_start_time</span> = microtime(<span>true</span>); <span>$selection_sort</span> = selectionSort(<span>$arr</span>); <span>$selection_end_time</span> = microtime(<span>true</span>); <span>$selection_need_time</span> = <span>$selection_end_time</span> - <span>$selection_start_time</span>; print_r(<span>"选择排序耗时:"</span> . <span>$selection_need_time</span> . <span>"<br />"</span>); <span>//4 并归排序</span><span>//merge函数将指定的两个有序数组(arr1arr2,)合并并且排序</span><span>//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据</span><span><span>function</span><span>al_merge</span><span>(<span>$arrA</span>, <span>$arrB</span>)</span> {</span><span>$arrC</span> = <span>array</span>(); <span>while</span> (count(<span>$arrA</span>) && count(<span>$arrB</span>)) { <span>//这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,</span><span>//不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用</span><span>$arrC</span>[] = <span>$arrA</span>[<span>'0'</span>] < <span>$arrB</span>[<span>'0'</span>] ? array_shift(<span>$arrA</span>) : array_shift(<span>$arrB</span>); } <span>return</span> array_merge(<span>$arrC</span>, <span>$arrA</span>, <span>$arrB</span>); } <span>//归并排序主程序</span><span><span>function</span><span>al_merge_sort</span><span>(<span>$arr</span>)</span> {</span><span>$len</span> = count(<span>$arr</span>); <span>if</span> (<span>$len</span> <= <span>1</span>) <span>return</span><span>$arr</span>;<span>//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组</span><span>$mid</span> = intval(<span>$len</span> / <span>2</span>);<span>//取数组中间</span><span>$left_arr</span> = array_slice(<span>$arr</span>, <span>0</span>, <span>$mid</span>);<span>//拆分数组0-mid这部分给左边left_arr</span><span>$right_arr</span> = array_slice(<span>$arr</span>, <span>$mid</span>);<span>//拆分数组mid-末尾这部分给右边right_arr</span><span>$left_arr</span> = al_merge_sort(<span>$left_arr</span>);<span>//左边拆分完后开始递归合并往上走</span><span>$right_arr</span> = al_merge_sort(<span>$right_arr</span>);<span>//右边拆分完毕开始递归往上走</span><span>$arr</span> = al_merge(<span>$left_arr</span>, <span>$right_arr</span>);<span>//合并两个数组,继续递归</span><span>return</span><span>$arr</span>; } <span>$merge_start_time</span> = microtime(<span>true</span>); <span>$merge_sort</span> = al_merge_sort(<span>$arr</span>); <span>$merge_end_time</span> = microtime(<span>true</span>); <span>$merge_need_time</span> = <span>$merge_end_time</span> - <span>$merge_start_time</span>; print_r(<span>"并归排序耗时:"</span> . <span>$merge_need_time</span> . <span>"<br />"</span>); <span>//5 快速排序</span><span><span>function</span><span>quickSort</span><span>(&<span>$arr</span>)</span>{</span><span>if</span>(count(<span>$arr</span>)><span>1</span>){ <span>$k</span>=<span>$arr</span>[<span>0</span>]; <span>$x</span>=<span>array</span>(); <span>$y</span>=<span>array</span>(); <span>$_size</span>=count(<span>$arr</span>); <span>for</span>(<span>$i</span>=<span>1</span>;<span>$i</span><<span>$_size</span>;<span>$i</span>++){ <span>if</span>(<span>$arr</span>[<span>$i</span>]<=<span>$k</span>){ <span>$x</span>[]=<span>$arr</span>[<span>$i</span>]; }<span>elseif</span>(<span>$arr</span>[<span>$i</span>]><span>$k</span>){ <span>$y</span>[]=<span>$arr</span>[<span>$i</span>]; } } <span>$x</span>=quickSort(<span>$x</span>); <span>$y</span>=quickSort(<span>$y</span>); <span>return</span> array_merge(<span>$x</span>,<span>array</span>(<span>$k</span>),<span>$y</span>); }<span>else</span>{ <span>return</span><span>$arr</span>; } } <span>$quick_start_time</span> = microtime(<span>true</span>); <span>$quick_sort</span> = al_merge_sort(<span>$arr</span>); <span>$quick_end_time</span> = microtime(<span>true</span>); <span>$quick_need_time</span> = <span>$quick_end_time</span> - <span>$quick_start_time</span>; print_r(<span>"快速排序耗时:"</span> . <span>$quick_need_time</span> . <span>"<br />"</span>); </code>
Time-consuming comparison
Insertion sort time-consuming: 1.2335460186005
Bubble sorting time: 2.6180219650269
Selection sorting time: 1.4159741401672
Merge sorting time: 0.17212891578674
Quick sort takes time: 0.16736888885498
References
The above introduces the implementation of classic algorithms in PHP, including PHP and classic aspects. I hope it will be helpful to friends who are interested in PHP tutorials.