php常用的排序算法与二分法查找
一 ： 归并排序
将两个的有序数列合并成一个有序数列，我们称之为”归并“。
归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括”从上往下“和”从下往上“2种方式。
1. 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果
2. 从上往下的归并排序：它与”从下往上”在排序上是反方向的。它基本包括3步：
① 分解 — 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 — 递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 — 将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]。
<span style="color: #008000"> /*</span><span style="color: #008000">* * 归并排序实现过程 * @param Array $arr 待排序的区间数组 * @param Int $start 第一个区间数组的起始位置 * @param Int $mid 第一个区间数组的结束位置，第二个区间数组的起始位置 * @param Int $end 第二个区间数组的结束位置 * @return void </span><span style="color: #008000">*/</span> <span style="color: #0000ff">function</span> merge(<span style="color: #0000ff">Array</span> &<span style="color: #800080">$arr</span>,<span style="color: #800080">$start</span>,<span style="color: #800080">$mid</span>,<span style="color: #800080">$end</span><span style="color: #000000">) { </span><span style="color: #800080">$i</span> = <span style="color: #800080">$start</span><span style="color: #000000">; </span><span style="color: #800080">$j</span> = <span style="color: #800080">$mid</span> + 1<span style="color: #000000">; </span><span style="color: #800080">$k</span> = 0<span style="color: #000000">; </span><span style="color: #0000ff">while</span>(<span style="color: #800080">$i</span> <= <span style="color: #800080">$mid</span> && <span style="color: #800080">$j</span> <= <span style="color: #800080">$end</span><span style="color: #000000">) { </span><span style="color: #0000ff">if</span> (<span style="color: #800080">$arr</span>[<span style="color: #800080">$i</span>] <= <span style="color: #800080">$arr</span>[<span style="color: #800080">$j</span>]) <span style="color: #008000">//</span><span style="color: #008000">判断两个区间数组各自数据的大小，并归类</span> <span style="color: #800080">$tmp</span>[<span style="color: #800080">$k</span>++] = <span style="color: #800080">$arr</span>[<span style="color: #800080">$i</span>++<span style="color: #000000">]; </span><span style="color: #0000ff">else</span> <span style="color: #800080">$tmp</span>[<span style="color: #800080">$k</span>++] = <span style="color: #800080">$arr</span>[<span style="color: #800080">$j</span>++<span style="color: #000000">]; } </span><span style="color: #0000ff">while</span>(<span style="color: #800080">$i</span> <= <span style="color: #800080">$mid</span>) <span style="color: #008000">//</span><span style="color: #008000">防止第一个区间有一个数据没有归类</span> <span style="color: #800080">$tmp</span>[<span style="color: #800080">$k</span>++] = <span style="color: #800080">$arr</span>[<span style="color: #800080">$i</span>++<span style="color: #000000">]; </span><span style="color: #0000ff">while</span>(<span style="color: #800080">$j</span> <= <span style="color: #800080">$end</span>) <span style="color: #008000">//</span><span style="color: #008000">防止第二个区间有一个数据没有归类</span> <span style="color: #800080">$tmp</span>[<span style="color: #800080">$k</span>++] = <span style="color: #800080">$arr</span>[<span style="color: #800080">$j</span>++<span style="color: #000000">]; </span><span style="color: #008000">//</span><span style="color: #008000"> 将排序后的元素，全部都整合到数组arr中。</span> <span style="color: #0000ff">for</span> (<span style="color: #800080">$i</span> = 0; <span style="color: #800080">$i</span> < <span style="color: #800080">$k</span>; ++<span style="color: #800080">$i</span><span style="color: #000000">) </span><span style="color: #800080">$arr</span>[<span style="color: #800080">$start</span> + <span style="color: #800080">$i</span>] = <span style="color: #800080">$tmp</span>[<span style="color: #800080">$i</span><span style="color: #000000">]; } </span><span style="color: #008000">/*</span><span style="color: #008000">* * 归并排序(从上往下) * @param Array $arr 待排序的数组 * @param Int $start 数组起始位置 * @param Int end 数组结束位置 * @return void </span><span style="color: #008000">*/</span> <span style="color: #0000ff">function</span> merge_sort(<span style="color: #0000ff">Array</span> &<span style="color: #800080">$arr</span>,<span style="color: #800080">$start</span>=0,<span style="color: #800080">$end</span>=0<span style="color: #000000">) { </span><span style="color: #800080">$len</span> = <span style="color: #008080">count</span>(<span style="color: #800080">$arr</span><span style="color: #000000">); </span><span style="color: #0000ff">if</span>(<span style="color: #800080">$len</span> <= 1 || <span style="color: #800080">$start</span> >= <span style="color: #800080">$end</span><span style="color: #000000">) </span><span style="color: #0000ff">return</span> <span style="color: #800080">$arr</span><span style="color: #000000">; </span><span style="color: #800080">$mid</span> = <span style="color: #008080">intval</span>((<span style="color: #800080">$start</span> + <span style="color: #800080">$end</span>) / 2); <span style="color: #008000">//</span><span style="color: #008000">分区间</span><span style="color: #000000"> merge_sort(</span><span style="color: #800080">$arr</span>,<strong style="color:transparent">本文来源gao@daima#com搞(%代@#码@网&</strong><strong>搞gaodaima代码</strong><span style="color: #800080">$start</span>,<span style="color: #800080">$mid</span><span style="color: #000000">); merge_sort(</span><span style="color: #800080">$arr</span>,<span style="color: #800080">$mid</span>+1,<span style="color: #800080">$end</span><span style="color: #000000">); merge(</span><span style="color: #800080">$arr</span>,<span style="color: #800080">$start</span>,<span style="color: #800080">$mid</span>,<span style="color: #800080">$end</span><span style="color: #000000">); }<br /><br /> //从下往上与此刚好相反</span>
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：php惯用的排序算法与二分法查找
转载请注明原文链接：php惯用的排序算法与二分法查找
