php实现二路归并排序 - 天空中的蜂蜂

<span style="color: #008080;"> 1</span> <span style="color: #800080;">$arr</span> = [9, 43, 12, 0, 87, 1<span style="color: #000000;">];
</span><span style="color: #008080;"> 2</span> <span style="color: #0000ff;">function</span> merge_sort(&<span style="color: #800080;">$arr</span><span style="color: #000000;">){
</span><span style="color: #008080;"> 3</span>     _merge_sort(<span style="color: #800080;">$arr</span>, <span style="color: #800080;">$arr</span>, 0, <span style="color: #008080;">count</span>(<span style="color: #800080;">$arr</span>) - 1<span style="color: #000000;">);
</span><span style="color: #008080;"> 4</span> <span style="color: #000000;">}
</span><span style="color: #008080;"> 5</span> 
<span style="color: #008080;"> 6</span> <span style="color: #0000ff;">function</span> _merge_sort(&<span style="color: #800080;">$s_arr</span>, &<span style="color: #800080;">$d_arr</span>, <span style="color: #800080;">$i</span>, <span style="color: #800080;">$j</span><span style="color: #000000;">){
</span><span style="color: #008080;"> 7</span>     <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$i</span> > <span style="color: #800080;">$j</span><span style="color: #000000;">){
</span><span style="color: #008080;"> 8</span>         <span style="color: #0000ff;">return</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 9</span> <span style="color: #000000;">    }
</span><span style="color: #008080;">10</span>     <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$i</span> == <span style="color: #800080;">$j</span><span style="color: #000000;">){
</span><span style="color: #008080;">11</span>         <span style="color: #0000ff;">echo</span> 'aa'<span style="color: #000000;">;
</span><span style="color: #008080;">12</span>         <span style="color: #800080;">$d_arr</span>[<span style="color: #800080;">$i</span>] = <span style="color: #800080;">$s_arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">];
</span><span style="color: #008080;">13</span>         <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;">14</span> <span style="color: #000000;">    }
</span><span style="color: #008080;">15</span>     <span style="color: #800080;">$tmp_arr</span> = <span style="color: #0000ff;">array</span><span style="color: #000000;">();
</span><span style="color: #008080;">16</span>     <span style="color: #800080;">$m</span> = <span style="color: #008080;">intval</span>((<span style="color: #800080;">$i</span> + <span style="color: #800080;">$j</span>)/2<span style="color: #000000;">);
</span><span style="color: #008080;">17</span>     <span style="color: #0000ff;">echo</span> <span style="color: #800080;">$m</span><span style="color: #000000;">;
</span><span style="color: #008080;">18</span>     <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$i</span> <= <span style="color: #800080;">$m</span><span style="color: #000000;">){
</span><span style="color: #008080;">19</span>         _merge_sort(<span style="color: #800080;">$s_arr</span>, <span style="color: #800080;">$tmp_arr</span>, <span style="color: #800080;">$i</span>, <span style="color: #800080;">$m</span><span style="color: #000000;">);
</span><span style="color: #008080;">20</span> <span style="color: #000000;">    }
</span><span style="color: #008080;">21</span>     <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$m</span>+1 <= <span style="color: #800080;">$j</span><span style="color: #000000;"> ){
</span><span style="color: #008080;">22</span>         _merge_sort(<span style="color: #800080;">$s_arr</span>, <span style="color: #800080;">$tmp_arr</span>, <span style="color: #800080;">$m</span>+1, <span style="color: #800080;">$j</span><span style="color: #000000;">);
</span><span style="color: #008080;">23</span> <span style="color: #000000;">    }
</span><span style="color: #008080;">24</span>     merge(<span style="color: #800080;">$tmp_arr</span>, <span style="color: #800080;">$d_arr</span>, <span style="color: #800080;">$i</span>, <span style="color: #800080;">$m</span>, <span style="color: #800080;">$j</span><span style="color: #000000;">);
</span><span style="color: #008080;">25</span> <span style="color: #000000;">}
</span><span style="color: #008080;">26</span> //$s_arr中的$start到$m与$m到$end两个序列都是有序的，将这两个序列合并到$d_arr里面
<span style="color: #008080;">27</span> <span style="color: #0000ff;">function</span> merge(&<span style="color: #800080;">$s_arr</span>, &<span style="color: #800080;">$d_arr</span>, <span style="color: #800080;">$start</span>, <span style="color: #800080;">$m</span>, <span style="color: #800080;">$end</span><span style="color: #000000;">){
</span><span style="color: #008080;">28</span>     <span style="color: #800080;">$i</span> = <span style="color: #800080;">$start</span>; <span style="color: #800080;">$j</span> = <span style="color: #800080;">$m</span>+1;<span style="color: #800080;">$d_i</span> = <span style="color: #800080;">$i</span><span style="color: #000000;">;
</span><span style="color: #008080;">29</span>     <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> <= <span style="color: #800080;">$m</span> && <span style="color: #800080;">$j</span> <= <span style="color: #800080;">$end</span><span style="color: #000000;">){
</span><span style="color: #008080;">30</span>         <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$s_arr</span>[<span style="color: #800080;">$i</span>] > <span style="color: #800080;">$s_arr</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">]){
</span><span style="color: #008080;">31</span>             <span style="color: #800080;">$d_arr</span>[<span style="color: #800080;">$d_i</span>++] = <span style="color: #800080;">$s_arr</span>[<span style="color: #800080;">$i</span>++<span style="color: #000000;">];
</span><span style="color: #008080;">32</span>             <span style="color: #008000;">//</span><span style="color: #008000;">$i++;</span>
<span style="color: #008080;">33</span>         }<span style="color: #0000ff;">else</span><span style="color: #000000;">{
</span><span style="color: #008080;">34</span>             <span style="color: #800080;">$d_arr</span>[<span style="color: #800080;">$d_i</span>++] = <span style="color: #800080;">$s_arr</span>[<span style="color: #800080;">$j</span>++<span style="color: #000000;">];
</span><span style="color: #008080;">35</span> <span style="color: #000000;">        }
</span><span style="color: #008080;">36</span> <span style="color: #000000;">    }
</span><span style="color: #008080;">37</span>     <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> <= <span style="color: #800080;">$m</span><span style="color: #000000;">){
</span><span style="color: #008080;">38</span>         <span style="color: #800080;">$d_arr</span>[<span style="color: #800080;">$d_i</span>++] = <span style="color: #800080;">$s_arr</span>[<span style="color: #800080;">$i</span>++<span style="color: #000000;">];
</span><span style="color: #008080;">39</span>         <span style="color: #008000;">//</span><span style="color: #008000;">$i++;</span>
<span style="color: #008080;">40</span> <span style="color: #000000;">    }
</span><span style="color: #008080;">41</span>     <span style="color: #0000ff;">while</span> (<span style="color: #800080;">$j</span> <= <span style="color: #800080;">$end</span><span style="color: #000000;">) {
</span><span style="color: #008080;">42</span>         <span style="color: #800080;">$d_arr</span>[<span style="color: #800080;">$d_i</span>++] = <span style="color: #800080;">$s_arr</span>[<span style="color: #800080;">$j</span>++<span style="color: #000000;">];
</span><span style="color: #008080;">43</span> <span style="color: #000000;">    }
</span><span style="color: #008080;">44</span> }