찾다
집php教程php手册php常用的排序算法与二分法查找，php算法二分法
php常用的排序算法与二分法查找，php算法二分法
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Jun 13, 2016 am 08:42 AM
php하나그리고둘종류찾다용적연산

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);

 

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
관련 기사
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法：1、使用abs()函数将负数转为正数，使用intval()函数对正数取整，转为正整数，语法“intval(abs($number))”；2、利用“~”位运算符将负数取反加一，语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法：1、使用“sleep(延迟秒数)”语句，可延迟执行函数若干秒；2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句，可延迟执行函数若干秒和纳秒；3、使用“time_sleep_until(time()+7)”语句。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中，下标不仅可以应用于数组和对象，还可应用于字符串，利用字符串的下标和中括号“[]”可以访问指定索引位置的字符，并对该字符进行读写，语法“字符串名[下标值]”；字符串的下标值（索引值）只能是整数类型，起始值为0。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法：1、利用“/”运算符进行除法运算，语法“数值 / 100”；2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值，并保留两位小数。

php怎么读取字符串后几个字符php怎么读取字符串后几个字符Apr 22, 2022 pm 08:31 PM

在php中，可以使用substr()函数来读取字符串后几个字符，只需要将该函数的第二个参数设置为负值，第三个参数省略即可；语法为“substr(字符串,-n)”，表示读取从字符串结尾处向前数第n个字符开始，直到字符串结尾的全部字符。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法：1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式；2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的，因此真实天数需要在此基础上加1。

php怎么查找字符串是第几位php怎么查找字符串是第几位Apr 22, 2022 pm 06:48 PM

查找方法：1、用strpos()，语法“strpos("字符串值","查找子串")+1”；2、用stripos()，语法“strpos("字符串值","查找子串")+1”。因为字符串是从0开始计数的，因此两个函数获取的位置需要进行加1处理。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法：1、用“str_replace("&nbsp;","其他字符",$str)”语句，可将nbsp符替换为其他字符；2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

더보기

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
어 ass 신 크리드 그림자 : 조개 수수께끼 솔루션
1 몇 주 전ByDDD
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
더보기

뜨거운 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

DVWA

DVWA

DVWA(Damn Vulnerable Web App)는 매우 취약한 PHP/MySQL 웹 애플리케이션입니다. 주요 목표는 보안 전문가가 법적 환경에서 자신의 기술과 도구를 테스트하고, 웹 개발자가 웹 응용 프로그램 보안 프로세스를 더 잘 이해할 수 있도록 돕고, 교사/학생이 교실 환경 웹 응용 프로그램에서 가르치고 배울 수 있도록 돕는 것입니다. 보안. DVWA의 목표는 다양한 난이도의 간단하고 간단한 인터페이스를 통해 가장 일반적인 웹 취약점 중 일부를 연습하는 것입니다. 이 소프트웨어는

PhpStorm 맥 버전

PhpStorm 맥 버전

최신(2018.2.1) 전문 PHP 통합 개발 도구

Atom Editor Mac 버전 다운로드

Atom Editor Mac 버전 다운로드

가장 인기 있는 오픈 소스 편집기

MinGW - Windows용 미니멀리스트 GNU

MinGW - Windows용 미니멀리스트 GNU

이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.

더보기

뜨거운 주제

Gmail 이메일의 로그인 입구는 어디에 있나요?
7445
15
Cakephp 튜토리얼
1374
52
Steam의 계정 이름 형식은 무엇입니까?
76
11
Win11 활성화 키 영구
39
19
NYT 연결 힌트와 답변
14
6
더보기