コミュニティ
学ぶ
ツールライブラリ
AIツール
レジャー
検索
日本語
目次
php常用的排序算法与二分法查找，php算法二分法
ホームページ php教程 php手册 php常用的排序算法与二分法查找，php算法二分法

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Jun 13, 2016 am 08:42 AM
php 1つ そして 二 選別 探す 使用 アルゴリズム

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 までご連絡ください。

ホット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ヘンタイを無料で生成します。

もっと見る

人気の記事

R.E.P.O.説明されたエネルギー結晶と彼らが何をするか（黄色のクリスタル）
3週間前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最高のグラフィック設定
3週間前 By 尊渡假赌尊渡假赌尊渡假赌
アサシンのクリードシャドウズ：シーシェルリドルソリューション
1週間前 By DDD
R.E.P.O.誰も聞こえない場合はオーディオを修正する方法
3週間前 By 尊渡假赌尊渡假赌尊渡假赌
Atomfallのクレーンコントロールキーカードを見つける場所
1週間前 By DDD
もっと見る

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト（SublimeText3）

もっと見る

ホットトピック

Gmailメールのログイン入り口はどこですか？
7441
15
CakePHP チュートリアル
1371
52
Steamのアカウント名の形式は何ですか
76
11
Win11 Activation Key Permanent
33
19
もっと見る
Related knowledge
Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Dec 24, 2024 pm 04:42 PM

PHP 8.4 では、いくつかの新機能、セキュリティの改善、パフォーマンスの改善が行われ、かなりの量の機能の非推奨と削除が行われています。 このガイドでは、Ubuntu、Debian、またはその派生版に PHP 8.4 をインストールする方法、または PHP 8.4 にアップグレードする方法について説明します。

CakePHP の日付と時刻 CakePHP の日付と時刻 Sep 10, 2024 pm 05:27 PM

Cakephp4 で日付と時刻を操作するには、利用可能な FrozenTime クラスを利用します。

CakePHP データベースの操作 CakePHP データベースの操作 Sep 10, 2024 pm 05:25 PM

CakePHP でデータベースを操作するのは非常に簡単です。この章では、CRUD (作成、読み取り、更新、削除) 操作について理解します。

CakePHP ファイルのアップロード CakePHP ファイルのアップロード Sep 10, 2024 pm 05:27 PM

ファイルのアップロードを行うには、フォーム ヘルパーを使用します。ここではファイルアップロードの例を示します。

CakePHP について話し合う CakePHP について話し合う Sep 10, 2024 pm 05:28 PM

CakePHP は、PHP 用のオープンソース フレームワークです。これは、アプリケーションの開発、展開、保守をより簡単にすることを目的としています。 CakePHP は、強力かつ理解しやすい MVC のようなアーキテクチャに基づいています。モデル、ビュー、コントローラー

CakePHP バリデータの作成 CakePHP バリデータの作成 Sep 10, 2024 pm 05:26 PM

Validator は、コントローラーに次の 2 行を追加することで作成できます。

CakePHP のロギング CakePHP のロギング Sep 10, 2024 pm 05:26 PM

CakePHP へのログインは非常に簡単な作業です。使用する関数は 1 つだけです。 cronjob などのバックグラウンド プロセスのエラー、例外、ユーザー アクティビティ、ユーザーが実行したアクションをログに記録できます。 CakePHP でのデータのログ記録は簡単です。 log()関数が提供されています

PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 Dec 20, 2024 am 11:31 AM

Visual Studio Code (VS Code とも呼ばれる) は、すべての主要なオペレーティング システムで利用できる無料のソース コード エディター (統合開発環境 (IDE)) です。 多くのプログラミング言語の拡張機能の大規模なコレクションを備えた VS Code は、

See all articles