Community Learn Tools Library Leisure
search
English
Home > Backend Development > PHP Tutorial > php常用的排序算法与二分法查找，php算法二分法_PHP教程

php常用的排序算法与二分法查找，php算法二分法_PHP教程

WBOY
Release： 2016-07-12 08:54:53
Original
1028 people have browsed it

php常用的排序算法与二分法查找，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>    /*</span><span>*
      * 归并排序实现过程
      * @param Array $arr 待排序的区间数组
      * @param Int $start 第一个区间数组的起始位置
      * @param Int $mid 第一个区间数组的结束位置，第二个区间数组的起始位置
      * @param Int $end 第二个区间数组的结束位置
      * @return void
      </span><span>*/</span>
    <span>function</span> merge(<span>Array</span> &<span>$arr</span>,<span>$start</span>,<span>$mid</span>,<span>$end</span><span>)
    {
        </span><span>$i</span> = <span>$start</span><span>;
        </span><span>$j</span> = <span>$mid</span> + 1<span>;
        </span><span>$k</span> = 0<span>; 

        </span><span>while</span>(<span>$i</span> <= <span>$mid</span> && <span>$j</span> <= <span>$end</span><span>)
        {
            </span><span>if</span> (<span>$arr</span>[<span>$i</span>] <= <span>$arr</span>[<span>$j</span>])    <span>//</span><span>判断两个区间数组各自数据的大小，并归类</span>
                <span>$tmp</span>[<span>$k</span>++] = <span>$arr</span>[<span>$i</span>++<span>];
            </span><span>else</span>
                <span>$tmp</span>[<span>$k</span>++] = <span>$arr</span>[<span>$j</span>++<span>];
        }

        </span><span>while</span>(<span>$i</span> <= <span>$mid</span>)    <span>//</span><span>防止第一个区间有一个数据没有归类</span>
            <span>$tmp</span>[<span>$k</span>++] = <span>$arr</span>[<span>$i</span>++<span>];

        </span><span>while</span>(<span>$j</span> <= <span>$end</span>) <span>//</span><span>防止第二个区间有一个数据没有归类</span>
            <span>$tmp</span>[<span>$k</span>++] = <span>$arr</span>[<span>$j</span>++<span>];

        </span><span>//</span><span> 将排序后的元素，全部都整合到数组arr中。</span>
        <span>for</span> (<span>$i</span> = 0; <span>$i</span> < <span>$k</span>; ++<span>$i</span><span>)
            </span><span>$arr</span>[<span>$start</span> + <span>$i</span>] = <span>$tmp</span>[<span>$i</span><span>];
    }
    </span><span>/*</span><span>*
      * 归并排序(从上往下)
      * @param Array $arr 待排序的数组
      * @param Int $start 数组起始位置
      * @param Int end 数组结束位置
      * @return void
      </span><span>*/</span>
    <span>function</span> merge_sort(<span>Array</span> &<span>$arr</span>,<span>$start</span>=0,<span>$end</span>=0<span>)
    {
        </span><span>$len</span> = <span>count</span>(<span>$arr</span><span>);
        </span><span>if</span>(<span>$len</span> <= 1 || <span>$start</span> >= <span>$end</span><span>)
            </span><span>return</span> <span>$arr</span><span>;
        </span><span>$mid</span> = <span>intval</span>((<span>$start</span> + <span>$end</span>) / 2); <span>//</span><span>分区间</span>
<span>    
        merge_sort(</span><span>$arr</span>,<span>$start</span>,<span>$mid</span><span>);
        merge_sort(</span><span>$arr</span>,<span>$mid</span>+1,<span>$end</span><span>);

        merge(</span><span>$arr</span>,<span>$start</span>,<span>$mid</span>,<span>$end</span><span>);
    }<br /><br />   //从下往上与此刚好相反</span>
Copy after login

二 ： 快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序主体算法时间运算量约 O(log2n) ，划分子区函数运算量约 O(n) ，所以总的时间复杂度为 O(nlog2n) ，它显然优于冒泡排序 O(n2). 可是算法的优势并不是绝对的。试分析，当原文件关键字有序时，快速排序时间复杂度是 O(n2), 这种情况下快速排序不快。而这种情况的冒泡排序是 O(n), 反而很快。在原文件记录关键字无序时的多种排序方法中，快速排序被认为是最好的一种排序方法。

<span>    /*</span><span>*
      * 快速排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      </span><span>*/</span>
    <span>function</span> quick_sort(<span>Array</span> <span>$arr</span><span>)
    {
        </span><span>$len</span> = <span>count</span>(<span>$arr</span><span>);
        </span><span>if</span>(<span>$len</span> <= 1<span>)
            </span><span>return</span> <span>$arr</span><span>;
        </span><span>$tmp</span> = <span>$arr</span>[0<span>];
        </span><span>$left_arr</span> =<span> [];
        </span><span>$right_arr</span> =<span> [];
        </span><span>for</span>(<span>$i</span> = 1; <span>$i</span> < <span>$len</span>; ++<span>$i</span><span>)
        {
            </span><span>if</span>(<span>$arr</span>[<span>$i</span>] <= <span>$tmp</span><span>)
                </span><span>$left_arr</span>[] = <span>$arr</span>[<span>$i</span><span>];
            </span><span>else</span>
                <span>$right_arr</span>[] = <span>$arr</span>[<span>$i</span><span>];
        }
        </span><span>//</span><span>递归分类</span>
        <span>$left_arr</span> = quick_sort(<span>$left_arr</span><span>);
        </span><span>$right_arr</span> = quick_sort(<span>$right_arr</span><span>);

        </span><span>return</span> <span>array_merge</span>(<span>$left_arr</span>,<span>array</span>(<span>$tmp</span>),<span>$right_arr</span><span>);
    }
    </span>
Copy after login

三 ：冒泡排序

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。该算法的时间复杂度为O(n2)。但是，当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O(n)。

<span>    /*</span><span>*
      * 冒泡排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      </span><span>*/</span>
    <span>function</span> bubble_sort(<span>Array</span> <span>$arr</span><span>)
    {
        </span><span>$len</span> = <span>count</span>(<span>$arr</span><span>);
        </span><span>for</span>(<span>$i</span> = 0; <span>$i</span> < <span>$len</span>; ++<span>$i</span><span>)
        {
            </span><span>for</span>(<span>$j</span> = <span>$len</span> - 1; <span>$j</span> > <span>$i</span>; --<span>$j</span><span>)
            {
                </span><span>if</span>(<span>$arr</span>[<span>$j</span>] < <span>$arr</span>[<span>$j</span>-1<span>])
                {
                    </span><span>$tmp</span> = <span>$arr</span>[<span>$j</span><span>];
                    </span><span>$arr</span>[<span>$j</span>] = <span>$arr</span>[<span>$j</span>-1<span>];
                    </span><span>$arr</span>[<span>$j</span>-1] = <span>$tmp</span><span>;
                }
            }
        }
        </span><span>return</span> <span>$arr</span><span>;
    }</span>
Copy after login

四 ：插入排序

每次将一个待排序的数据元素插入到前面已经排好序的数列中，使数列依然有序，知道待排序数据元素全部插入完为止。如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择

<span>    /*</span><span>*
      * 插入排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      </span><span>*/</span>
    <span>function</span> insert_sort(<span>Array</span> <span>$arr</span><span>)
    {
        </span><span>$len</span> = <span>count</span>(<span>$arr</span><span>);
        </span><span>for</span>(<span>$i</span> = 1; <span>$i</span> < <span>$len</span>; ++<span>$i</span><span>)
        {
            </span><span>$tmp</span> = <span>$arr</span>[<span>$i</span><span>];
            </span><span>$j</span> = <span>$i</span> - 1<span>;
            </span><span>//</span><span>把数据插入到合适的位置(交换位置)</span>
            <span>while</span>(<span>$j</span> >= 0 && <span>$arr</span>[<span>$j</span>] > <span>$tmp</span><span>)
            {
                </span><span>$arr</span>[<span>$j</span>+1] = <span>$arr</span>[<span>$j</span><span>];
                </span><span>$arr</span>[<span>$j</span>] = <span>$tmp</span><span>;
                </span>--<span>$j</span><span>;
            }
        }
        </span><span>return</span> <span>$arr</span><span>;
    }</span>
Copy after login

五 ：选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。时间复杂度为o(n2),不稳定排序，适合规模比较小的

<span>    /*</span><span>*
      * 选择排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      </span><span>*/</span>
    <span>function</span> select_sort(<span>Array</span> <span>$arr</span><span>)
    {
        </span><span>$len</span> = <span>count</span>(<span>$arr</span><span>);
        </span><span>for</span>(<span>$i</span> = 0; <span>$i</span> < <span>$len</span>; ++<span>$i</span><span>)
        {
            </span><span>$k</span> = <span>$i</span>;    <span>//</span><span>标记当前索引</span>
            <span>for</span>(<span>$j</span> = <span>$i</span> + 1; <span>$j</span> < <span>$len</span>; ++<span>$j</span><span>)
            {
                </span><span>if</span>(<span>$arr</span>[<span>$j</span>] < <span>$arr</span>[<span>$k</span><span>])
                    </span><span>$k</span> = <span>$j</span>; <span>//</span><span>获取当前最小值索引</span>
                <span>if</span>(<span>$k</span> != <span>$i</span>) <span>//</span><span>如果最小值得索引发生变化</span>
<span>                {
                    </span><span>$tmp</span> = <span>$arr</span>[<span>$i</span><span>];
                    </span><span>$arr</span>[<span>$i</span>] = <span>$arr</span>[<span>$k</span><span>];
                    </span><span>$arr</span>[<span>$k</span>] = <span>$tmp</span><span>;
                }
            }
        }
        </span><span>return</span> <span>$arr</span><span>;
    }</span>
Copy after login

六 ：二分查找

<span>    /*</span><span>*
      * 二分查找
      * @param Array $arr 待查找的数组
      * @param Int $key 要查找的关键字
      * @return Int
      </span><span>*/</span>
    <span>function</span> bin_search(<span>Array</span> <span>$arr</span>,<span>$key</span><span>)
    {
        </span><span>$high</span> = <span>count</span>(<span>$arr</span><span>);
        </span><span>if</span>(<span>$high</span> <= 0<span>)
            </span><span>return</span> 0<span>;
        </span><span>$low</span> = 0<span>;
        </span><span>while</span>(<span>$low</span> <= <span>$high</span><span>)
        {     
            </span><span>//</span><span>当前查找区间arr[low..high]非空</span>
              <span>$mid</span>=<span>intval</span>((<span>$low</span> + <span>$high</span>) / 2<span>);
            </span><span>if</span>(<span>$arr</span>[<span>$mid</span>] == <span>$key</span><span>) 
                </span><span>return</span> <span>$mid</span>; <span>//</span><span>查找成功返回</span>
            <span>if</span>(<span>$arr</span>[<span>$mid</span>] > <span>$key</span><span>)
                </span><span>$high</span> = <span>$mid</span> - 1; <span>//</span><span>继续在arr[low..mid-1]中查找</span>
            <span>else</span>
                <span>$low</span> = <span>$mid</span> + 1; <span>//</span><span>继续在arr[mid+1..high]中查找</span>
<span>        }
        </span><span>return</span> 0; <span>//</span><span>当low>high时表示查找区间为空，查找失败</span>
<span>    }
    </span><span>$arr</span> = <span>array</span>(1,2,4,6,10,40,50,80,100,110<span>);
    </span><span>echo</span> bin_search(<span>$arr</span>,80);
Copy after login

 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/1117674.htmlTechArticlephp常用的排序算法与二分法查找，php算法二分法 一 ： 归并排序 将两个的有序数列合并成一个有序数列，我们称之为" 归并 "。 归并排序...
Related labels：
php one and two sort Find use algorithm
source：php.cn
Previous article：Windows scheduled execution of PHP skills, windowsphp skills_PHP tutorial Next article：[Laravel] Laravel的基本使用，laravel使用_PHP教程
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
PHP arrays obtained from URL parameters do not behave as expected I have a URL parameter that contains the category ID and I want to treat it as an array li...
From 2024-04-06 22:09:02
0
1
1428
Where should I place CustomLog directive in apache I'm using php:7.2-apachedocker. I need to disable health check url login access log. Based...
From 2024-04-06 22:03:59
0
1
990
What is the format of the variables in the return value? I am a new learner of php. I found a piece of code: if($x<time()){return[false,'error']...
From 2024-04-06 21:55:20
0
1
778
Problems encountered when using opentbs to generate odt files: values ​​of the same key are displayed in the same row instead of separate columns. I'm using a library called OpenTbs to create odt using PHP, I'm using it because columns a...
From 2024-04-06 20:18:18
0
1
483
Group MySQL results by ID for looping over I have a table with flight data in mysql. I'm writing a php code that will group and displ...
From 2024-04-06 17:27:56
0
1
406
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template