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.

• Insertion sort
• Bubble sort
• Selection sort
• Merge sort
• Quick sort

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

• Introduction to Algorithms

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); });

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.