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> $mid && <span style="color: #800080;">$j</span> $end<span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] $arr[<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> $mid) <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> $end) <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> $k; ++<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> $start >= <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>,<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>二 ： 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序主体算法时间运算量约 O(log2n) ，划分子区函数运算量约 O(n) ，所以总的时间复杂度为 O(nlog2n) ，它显然优于冒泡排序 O(n2). 可是算法的优势并不是绝对的。试分析，当原文件关键字有序时，快速排序时间复杂度是 O(n2), 这种情况下快速排序不快。而这种情况的冒泡排序是 O(n), 反而很快。在原文件记录关键字无序时的多种排序方法中，快速排序被认为是最好的一种排序方法。
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 快速排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> quick_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><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> ) <span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[0<span style="color: #000000;">]; </span><span style="color: #800080;">$left_arr</span> =<span style="color: #000000;"> []; </span><span style="color: #800080;">$right_arr</span> =<span style="color: #000000;"> []; </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 1; <span style="color: #800080;">$i</span> $len; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] $tmp<span style="color: #000000;">) </span><span style="color: #800080;">$left_arr</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;">$right_arr</span>[] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; } </span><span style="color: #008000;">//</span><span style="color: #008000;">递归分类</span> <span style="color: #800080;">$left_arr</span> = quick_sort(<span style="color: #800080;">$left_arr</span><span style="color: #000000;">); </span><span style="color: #800080;">$right_arr</span> = quick_sort(<span style="color: #800080;">$right_arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">return</span> <span style="color: #008080;">array_merge</span>(<span style="color: #800080;">$left_arr</span>,<span style="color: #0000ff;">array</span>(<span style="color: #800080;">$tmp</span>),<span style="color: #800080;">$right_arr</span><span style="color: #000000;">); } </span>三 ：冒泡排序
两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。该算法的时间复杂度为O(n2)。但是，当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O(n)。
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 冒泡排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> bubble_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><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;">for</span>(<span style="color: #800080;">$i</span> = 0; <span style="color: #800080;">$i</span> $len; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span> = <span style="color: #800080;">$len</span> - 1; <span style="color: #800080;">$j</span> > <span style="color: #800080;">$i</span>; --<span style="color: #800080;">$j</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] $arr[<span style="color: #800080;">$j</span>-1<span style="color: #000000;">]) { </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>-1<span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>-1] = <span style="color: #800080;">$tmp</span><span style="color: #000000;">; } } } </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; }</span>四 ：插入排序
每次将一个待排序的数据元素插入到前面已经排好序的数列中，使数列依然有序，知道待排序数据元素全部插入完为止。如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 插入排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> insert_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><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;">for</span>(<span style="color: #800080;">$i</span> = 1; <span style="color: #800080;">$i</span> $len; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; </span><span style="color: #800080;">$j</span> = <span style="color: #800080;">$i</span> - 1<span style="color: #000000;">; </span><span style="color: #008000;">//</span><span style="color: #008000;">把数据插入到合适的位置(交换位置)</span> <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$j</span> >= 0 && <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] > <span style="color: #800080;">$tmp</span><span style="color: #000000;">) { </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>+1] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] = <span style="color: #800080;">$tmp</span><span style="color: #000000;">; </span>--<span style="color: #800080;">$j</span><span style="color: #000000;">; } } </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; }</span>五 ：选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。时间复杂度为o(n2),不稳定排序，适合规模比较小的
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 选择排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> select_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><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;">for</span>(<span style="color: #800080;">$i</span> = 0; <span style="color: #800080;">$i</span> $len; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #800080;">$k</span> = <span style="color: #800080;">$i</span>; <span style="color: #008000;">//</span><span style="color: #008000;">标记当前索引</span> <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span> = <span style="color: #800080;">$i</span> + 1; <span style="color: #800080;">$j</span> $len; ++<span style="color: #800080;">$j</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] $arr[<span style="color: #800080;">$k</span><span style="color: #000000;">]) </span><span style="color: #800080;">$k</span> = <span style="color: #800080;">$j</span>; <span style="color: #008000;">//</span><span style="color: #008000;">获取当前最小值索引</span> <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$k</span> != <span style="color: #800080;">$i</span>) <span style="color: #008000;">//</span><span style="color: #008000;">如果最小值得索引发生变化</span><span style="color: #000000;"> { </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>] = <span style="color: #800080;">$tmp</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: #008000;"> /*</span><span style="color: #008000;">* * 二分查找 * @param Array $arr 待查找的数组 * @param Int $key 要查找的关键字 * @return Int </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> bin_search(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span>,<span style="color: #800080;">$key</span><span style="color: #000000;">) { </span><span style="color: #800080;">$high</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;">$high</span> ) <span style="color: #0000ff;">return</span> 0<span style="color: #000000;">; </span><span style="color: #800080;">$low</span> = 0<span style="color: #000000;">; </span><span style="color: #0000ff;">while</span>(<span style="color: #800080;">$low</span> $high<span style="color: #000000;">) { </span><span style="color: #008000;">//</span><span style="color: #008000;">当前查找区间arr[low..high]非空</span> <span style="color: #800080;">$mid</span>=<span style="color: #008080;">intval</span>((<span style="color: #800080;">$low</span> + <span style="color: #800080;">$high</span>) / 2<span style="color: #000000;">); </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$mid</span>] == <span style="color: #800080;">$key</span><span style="color: #000000;">) </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$mid</span>; <span style="color: #008000;">//</span><span style="color: #008000;">查找成功返回</span> <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$mid</span>] > <span style="color: #800080;">$key</span><span style="color: #000000;">) </span><span style="color: #800080;">$high</span> = <span style="color: #800080;">$mid</span> - 1; <span style="color: #008000;">//</span><span style="color: #008000;">继续在arr[low..mid-1]中查找</span> <span style="color: #0000ff;">else</span> <span style="color: #800080;">$low</span> = <span style="color: #800080;">$mid</span> + 1; <span style="color: #008000;">//</span><span style="color: #008000;">继续在arr[mid+1..high]中查找</span><span style="color: #000000;"> } </span><span style="color: #0000ff;">return</span> 0; <span style="color: #008000;">//</span><span style="color: #008000;">当low>high时表示查找区间为空，查找失败</span><span style="color: #000000;"> } </span><span style="color: #800080;">$arr</span> = <span style="color: #0000ff;">array</span>(1,2,4,6,10,40,50,80,100,110<span style="color: #000000;">); </span><span style="color: #0000ff;">echo</span> bin_search(<span style="color: #800080;">$arr</span>,80);
Comment utiliser la fonction mid
Comment utiliser le retour en langage C
Utilisation de la valeur de retour Python
Utilisation du booléen en Java
utilisation du nœud clone
Quelle est la devise du PROM ?
Que signifie le réseau Apple LTE ?
Comment enregistrer un nom de domaine permanent pour un site Web
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
