지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > 백엔드 개발 > PHP 튜토리얼 > php常用的排序算法与二分法查找，php算法二分法_PHP教程

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

WBOY
풀어 주다： 2016-07-12 08:54:53
원래의
1028명이 탐색했습니다.

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>
로그인 후 복사

二 ： 快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序主体算法时间运算量约 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>
로그인 후 복사

三 ：冒泡排序

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。该算法的时间复杂度为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>
로그인 후 복사

四 ：插入排序

每次将一个待排序的数据元素插入到前面已经排好序的数列中，使数列依然有序，知道待排序数据元素全部插入完为止。如果目标是把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>
로그인 후 복사

五 ：选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。时间复杂度为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>
로그인 후 복사

六 ：二分查找

<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);
로그인 후 복사

 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/1117674.htmlTechArticlephp常用的排序算法与二分法查找，php算法二分法 一 ： 归并排序 将两个的有序数列合并成一个有序数列，我们称之为" 归并 "。 归并排序...
관련 라벨：
php 하나 그리고 둘 종류 찾다 용적 연산
원천：php.cn
이전 기사：windows定时执行PHP的技巧，windowsphp技巧_PHP教程 다음 기사：[Laravel] Laravel的基本使用，laravel使用_PHP教程
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
URL 매개변수에서 얻은 PHP 배열이 예상대로 작동하지 않습니다. 카테고리 ID가 포함된 URL 매개변수가 있고 이를 다음과 같은 배열로 처리하려고 합니다. http://example.com?cat[]=3,9,13 PHP에서는 ...
에서 2024-04-06 22:09:02
0
1
1428
Apache에서 CustomLog 지시문을 어디에 배치해야 합니까? 저는 php:7.2-apachedocker를 사용하고 있습니다. 상태 확인 URL 로그인 액세스 로그를 비활성화해야 합니다. 이 링크를 기반으로 Customlog...
에서 2024-04-06 22:03:59
0
1
990
반환 값의 변수 형식은 무엇입니까? 저는 PHP를 처음 배우는 사람입니다. 코드 조각을 찾았습니다: if($x<time()){return[false,'error'];} 논리나 변수는 중요하지 ...
에서 2024-04-06 21:55:20
0
1
778
opentbs를 사용하여 odt 파일을 생성할 때 발생하는 문제: 동일한 키의 값이 별도의 열이 아닌 동일한 행에 표시됩니다. PHP를 사용하여 odt를 만들기 위해 OpenTbs라는 라이브러리를 사용하고 있는데, 열과 행이 동적으로 생성되기 때문에 사용하고 있습니다. 행과 열을 만드는 ...
에서 2024-04-06 20:18:18
0
1
483
루프 오버를 위해 ID별로 MySQL 결과 그룹화 mysql에 비행 데이터가 포함된 테이블이 있습니다. codeigniter3 travel_idair_idFlightDurationout_or_inflightdur...
에서 2024-04-06 17:27:56
0
1
406
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿