PHP 言語で実装された 7 つの基本的な並べ替えメソッド

PHP 言語で実装した 7 つの基本的なソート方法

今日はよく使われる 7 つのソート方法をまとめて PHP 言語で実装しました。

1. 直接挿入ソート

   <span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008080;"> 2</span> <span style="color: #008000;"> *    直接插入排序,插入排序的思想是：当前插入位置之前的元素有序，</span><span style="color: #008080;"> 3</span> <span style="color: #008000;"> *    若插入当前位置的元素比有序元素最后一个元素大，则什么也不做，</span><span style="color: #008080;"> 4</span> <span style="color: #008000;"> *    否则在有序序列中找到插入的位置，并插入</span><span style="color: #008080;"> 5</span>  <span style="color: #008000;">*/</span><span style="color: #008080;"> 6</span> <span style="color: #0000ff;">function</span> insertSort(<span style="color: #800080;">$arr</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 7</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: #008080;"> 8</span>     <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 1; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$len</span>; <span style="color: #800080;">$i</span>++<span style="color: #000000;">) {</span><span style="color: #008080;"> 9</span>         <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>-1] > <span style="color: #800080;">$arr</span><span style="color: #000000;">[i]) {</span><span style="color: #008080;">10</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> >= 0; <span style="color: #800080;">$j</span>--<span style="color: #000000;"> ) {</span><span style="color: #008080;">11</span>                 <span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>+1<span style="color: #000000;">];</span><span style="color: #008080;">12</span>                 <span style="color: #0000ff;">if</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: #008080;">13</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: #008080;">14</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: #008080;">15</span>                 }<span style="color: #0000ff;">else</span><span style="color: #000000;">{</span><span style="color: #008080;">16</span>                     <span style="color: #0000ff;">break</span><span style="color: #000000;">;</span><span style="color: #008080;">17</span> <span style="color: #000000;">                }                    </span><span style="color: #008080;">18</span> <span style="color: #000000;">            }    </span><span style="color: #008080;">19</span> <span style="color: #000000;">        }</span><span style="color: #008080;">20</span> <span style="color: #000000;">    }    </span><span style="color: #008080;">21</span>     <span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">;</span><span style="color: #008080;">22</span> }

2. バブルソート

   <span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008080;"> 2</span> <span style="color: #008000;">    冒泡排序,冒泡排序思想：进行 n-1 趟冒泡排序， 每趟两两比较调整最大值到数组（子数组）末尾</span><span style="color: #008080;"> 3</span> <span style="color: #008000;">*/</span><span style="color: #008080;"> 4</span> <span style="color: #0000ff;">function</span> bubbleSort(<span style="color: #800080;">$arr</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 5</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: #008080;"> 6</span>     <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 1; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$len</span>; <span style="color: #800080;">$i</span>++<span style="color: #000000;">) {</span><span style="color: #008080;"> 7</span>         <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span> = 0; <span style="color: #800080;">$j</span> < <span style="color: #800080;">$len</span>-<span style="color: #800080;">$i</span>; <span style="color: #800080;">$j</span>++<span style="color: #000000;">) {</span><span style="color: #008080;"> 8</span>             <span style="color: #0000ff;">if</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: #008080;"> 9</span>                 <span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>+1<span style="color: #000000;">];</span><span style="color: #008080;">10</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: #008080;">11</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: #008080;">12</span> <span style="color: #000000;">            }</span><span style="color: #008080;">13</span> <span style="color: #000000;">        }</span><span style="color: #008080;">14</span> <span style="color: #000000;">    }</span><span style="color: #008080;">15</span>     <span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">;</span><span style="color: #008080;">16</span> }    

3. 単純選択ソート

   <span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008080;"> 2</span> <span style="color: #008000;">    简单选择排序, 简单排序思想：从数组第一个元素开始依次确定从小到大的元素</span><span style="color: #008080;"> 3</span> <span style="color: #008000;">*/</span><span style="color: #008080;"> 4</span> <span style="color: #0000ff;">function</span> selectSort(<span style="color: #800080;">$arr</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 5</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: #008080;"> 6</span>     <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 0; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$len</span>; <span style="color: #800080;">$i</span>++<span style="color: #000000;">) {</span><span style="color: #008080;"> 7</span>         <span style="color: #800080;">$k</span> = <span style="color: #800080;">$i</span><span style="color: #000000;">;</span><span style="color: #008080;"> 8</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> < <span style="color: #800080;">$len</span>; <span style="color: #800080;">$j</span>++<span style="color: #000000;">) {</span><span style="color: #008080;"> 9</span>             <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</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: #008080;">10</span>                 <span style="color: #800080;">$k</span> = <span style="color: #800080;">$j</span><span style="color: #000000;">;</span><span style="color: #008080;">11</span> <span style="color: #000000;">            }</span><span style="color: #008080;">12</span> <span style="color: #000000;">        }</span><span style="color: #008080;">13</span>         <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$k</span> != <span style="color: #800080;">$i</span><span style="color: #000000;">) {</span><span style="color: #008080;">14</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: #008080;">15</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: #008080;">16</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: #008080;">17</span> <span style="color: #000000;">        }</span><span style="color: #008080;">18</span> <span style="color: #000000;">    }</span><span style="color: #008080;">19</span>     <span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">;</span><span style="color: #008080;">20</span> }

4. ヒルソート

   <span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008080;"> 2</span> <span style="color: #008000;">    希尔排序,希尔排序原理：将数组按指定步长分隔成若干子序列，然后分别对子序列进行排序（在这是直接）</span><span style="color: #008080;"> 3</span> <span style="color: #008000;">*/</span><span style="color: #008080;"> 4</span> <span style="color: #0000ff;">function</span> shellSort(<span style="color: #800080;">$arr</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 5</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: #008080;"> 6</span>     <span style="color: #800080;">$k</span> = <span style="color: #008080;">floor</span>(<span style="color: #800080;">$len</span>/2<span style="color: #000000;">);</span><span style="color: #008080;"> 7</span>     <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$k</span> > 0<span style="color: #000000;">) {</span><span style="color: #008080;"> 8</span>         <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 0; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$k</span>; <span style="color: #800080;">$i</span>++<span style="color: #000000;">) {</span><span style="color: #008080;"> 9</span>             <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span> = <span style="color: #800080;">$i</span>; <span style="color: #800080;">$j</span> < <span style="color: #800080;">$len</span>, (<span style="color: #800080;">$j</span> + <span style="color: #800080;">$k</span>) < <span style="color: #800080;">$len</span>; <span style="color: #800080;">$j</span> = <span style="color: #800080;">$j</span> + <span style="color: #800080;">$k</span><span style="color: #000000;">) {</span><span style="color: #008080;">10</span>                 <span style="color: #0000ff;">if</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>+<span style="color: #800080;">$k</span><span style="color: #000000;">]) {</span><span style="color: #008080;">11</span>                     <span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>+<span style="color: #800080;">$k</span><span style="color: #000000;">];</span><span style="color: #008080;">12</span>                     <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</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: #008080;">13</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: #008080;">14</span> <span style="color: #000000;">                }</span><span style="color: #008080;">15</span> <span style="color: #000000;">            }</span><span style="color: #008080;">16</span> <span style="color: #000000;">        }</span><span style="color: #008080;">17</span>         <span style="color: #800080;">$k</span> = <span style="color: #008080;">floor</span>(<span style="color: #800080;">$k</span>/2<span style="color: #000000;">);</span><span style="color: #008080;">18</span> <span style="color: #000000;">    }</span><span style="color: #008080;">19</span>     <span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">;</span><span style="color: #008080;">20</span> }

5. クイックソート

   <span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008080;"> 2</span> <span style="color: #008000;"> *    快速排序,快排思想：通过一趟排序将待排的记录分为两个独立的部分，其中一部分的记录的关键字均不大于</span><span style="color: #008080;"> 3</span> <span style="color: #008000;"> *    另一部分记录的关键字，然后再分别对这两部分记录继续进行快速排序，以达到整个序列有序，具体做法需要</span><span style="color: #008080;"> 4</span> <span style="color: #008000;"> *    每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。</span><span style="color: #008080;"> 5</span> <span style="color: #008000;"> *    quickSort($arr, 0, count($arr) -1);</span><span style="color: #008080;"> 6</span>  <span style="color: #008000;">*/</span><span style="color: #008080;"> 7</span> <span style="color: #0000ff;">function</span> quickSort(&<span style="color: #800080;">$arr</span>,<span style="color: #800080;">$low</span>,<span style="color: #800080;">$high</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 8</span>     <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$low</span> < <span style="color: #800080;">$high</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 9</span>         <span style="color: #800080;">$i</span> = <span style="color: #800080;">$low</span><span style="color: #000000;">;</span><span style="color: #008080;">10</span>         <span style="color: #800080;">$j</span> = <span style="color: #800080;">$high</span><span style="color: #000000;">;</span><span style="color: #008080;">11</span>         <span style="color: #800080;">$primary</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$low</span><span style="color: #000000;">];</span><span style="color: #008080;">12</span>         <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> < <span style="color: #800080;">$j</span><span style="color: #000000;">) {</span><span style="color: #008080;">13</span>             <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> < <span style="color: #800080;">$j</span> && <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] >= <span style="color: #800080;">$primary</span><span style="color: #000000;">) {</span><span style="color: #008080;">14</span>                 <span style="color: #800080;">$j</span>--<span style="color: #000000;">;</span><span style="color: #008080;">15</span> <span style="color: #000000;">            }</span><span style="color: #008080;">16</span>             <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$i</span> < <span style="color: #800080;">$j</span><span style="color: #000000;">) {</span><span style="color: #008080;">17</span>                 <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>++] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">];</span><span style="color: #008080;">18</span> <span style="color: #000000;">            }</span><span style="color: #008080;">19</span>             <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> < <span style="color: #800080;">$j</span> && <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] <= <span style="color: #800080;">$primary</span><span style="color: #000000;">) {</span><span style="color: #008080;">20</span>                 <span style="color: #800080;">$i</span>++<span style="color: #000000;">;</span><span style="color: #008080;">21</span> <span style="color: #000000;">            }</span><span style="color: #008080;">22</span>             <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$i</span> < <span style="color: #800080;">$j</span><span style="color: #000000;">) {</span><span style="color: #008080;">23</span>                 <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>--] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">];</span><span style="color: #008080;">24</span> <span style="color: #000000;">            }</span><span style="color: #008080;">25</span> <span style="color: #000000;">        }</span><span style="color: #008080;">26</span>         <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] = <span style="color: #800080;">$primary</span><span style="color: #000000;">;</span><span style="color: #008080;">27</span>         quickSort(<span style="color: #800080;">$arr</span>, <span style="color: #800080;">$low</span>, <span style="color: #800080;">$i</span>-1<span style="color: #000000;">);</span><span style="color: #008080;">28</span>         quickSort(<span style="color: #800080;">$arr</span>, <span style="color: #800080;">$i</span>+1, <span style="color: #800080;">$high</span><span style="color: #000000;">);</span><span style="color: #008080;">29</span> <span style="color: #000000;">    }</span><span style="color: #008080;">30</span> }

6. ヒープソート

   <span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008080;"> 2</span> <span style="color: #008000;">    堆排序</span><span style="color: #008080;"> 3</span> <span style="color: #008000;">*/</span><span style="color: #008080;"> 4</span> <span style="color: #008080;"> 5</span> <span style="color: #008000;">//</span><span style="color: #008000;"> 调整子堆的为大根堆的过程，$s为子堆的根的位置，$m为堆最后一个元素位置</span><span style="color: #008080;"> 6</span> <span style="color: #0000ff;">function</span> heapAdjust(&<span style="color: #800080;">$arr</span>, <span style="color: #800080;">$s</span>, <span style="color: #800080;">$m</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 7</span>     <span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$s</span><span style="color: #000000;">];</span><span style="color: #008080;"> 8</span>     <span style="color: #008000;">//</span><span style="color: #008000;"> 在调整为大根堆的过程中可能会影响左子堆或右子堆</span><span style="color: #008080;"> 9</span> <span style="color: #008000;">    // for循环的作用是要保证子堆也是大根堆</span><span style="color: #008080;">10</span>     <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span> = 2*<span style="color: #800080;">$s</span> + 1; <span style="color: #800080;">$j</span> <= <span style="color: #800080;">$m</span>; <span style="color: #800080;">$j</span> = 2*<span style="color: #800080;">$j</span> + 1<span style="color: #000000;">) {</span><span style="color: #008080;">11</span>         <span style="color: #008000;">//</span><span style="color: #008000;"> 找到根节点的左右孩子中的最大者，然后用这个最大者与根节点比较，</span><span style="color: #008080;">12</span> <span style="color: #008000;">        // 若大则进行调整，否则符合大根堆的 特点跳出循环    </span><span style="color: #008080;">13</span>         <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$j</span> < <span style="color: #800080;">$m</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: #008080;">14</span>             <span style="color: #800080;">$j</span>++<span style="color: #000000;">;</span><span style="color: #008080;">15</span> <span style="color: #000000;">        }</span><span style="color: #008080;">16</span>         <span style="color: #0000ff;">if</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: #008080;">17</span>             <span style="color: #0000ff;">break</span><span style="color: #000000;">;</span><span style="color: #008080;">18</span> <span style="color: #000000;">        }</span><span style="color: #008080;">19</span>         <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$s</span>] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">];</span><span style="color: #008080;">20</span>         <span style="color: #800080;">$s</span> = <span style="color: #800080;">$j</span><span style="color: #000000;">;</span><span style="color: #008080;">21</span> <span style="color: #000000;">    }</span><span style="color: #008080;">22</span>     <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$s</span>] = <span style="color: #800080;">$tmp</span><span style="color: #000000;">;</span><span style="color: #008080;">23</span> <span style="color: #000000;">}</span><span style="color: #008080;">24</span> <span style="color: #008080;">25</span> <span style="color: #008000;">//</span><span style="color: #008000;"> 堆排序</span><span style="color: #008080;">26</span> <span style="color: #0000ff;">function</span> heapSort(<span style="color: #800080;">$arr</span><span style="color: #000000;">) {</span><span style="color: #008080;">27</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: #008080;">28</span>     <span style="color: #008000;">//</span><span style="color: #008000;"> 依次从子堆开始调整堆为大根堆</span><span style="color: #008080;">29</span>     <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = <span style="color: #008080;">floor</span>(<span style="color: #800080;">$len</span>/2-1); <span style="color: #800080;">$i</span> >= 0; <span style="color: #800080;">$i</span>--<span style="color: #000000;">) {</span><span style="color: #008080;">30</span>         heapAdjust(<span style="color: #800080;">$arr</span>, <span style="color: #800080;">$i</span>, <span style="color: #800080;">$len</span>-1<span style="color: #000000;">);</span><span style="color: #008080;">31</span> <span style="color: #000000;">    }</span><span style="color: #008080;">32</span>     <span style="color: #008000;">//</span><span style="color: #008000;"> 依次把根节点调换至最后一个位置，再次调整堆为大根堆，找到次最大值，</span><span style="color: #008080;">33</span> <span style="color: #008000;">    // 依次类推得到一个有序数组</span><span style="color: #008080;">34</span>     <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$n</span> = <span style="color: #800080;">$len</span>-1; <span style="color: #800080;">$n</span> > 0; <span style="color: #800080;">$n</span>--<span style="color: #000000;">) {</span><span style="color: #008080;">35</span>         <span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$n</span><span style="color: #000000;">];</span><span style="color: #008080;">36</span>         <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$n</span>] = <span style="color: #800080;">$arr</span>[0<span style="color: #000000;">];</span><span style="color: #008080;">37</span>         <span style="color: #800080;">$arr</span>[0] = <span style="color: #800080;">$tmp</span><span style="color: #000000;">;</span><span style="color: #008080;">38</span>         heapAdjust(<span style="color: #800080;">$arr</span>, 0, <span style="color: #800080;">$n</span>-1<span style="color: #000000;">);</span><span style="color: #008080;">39</span> <span style="color: #000000;">    }</span><span style="color: #008080;">40</span>     <span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">;</span><span style="color: #008080;">41</span> }

7. マージソート

   <span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008080;"> 2</span> <span style="color: #008000;">    归并排序,这里实现的是两路归并</span><span style="color: #008080;"> 3</span> <span style="color: #008000;">*/</span><span style="color: #008080;"> 4</span> <span style="color: #008000;">//</span><span style="color: #008000;"> 分别将有序的$arr1[s..m]、$arr2[m+1..n]归并为有序的$arr2[s..n]</span><span style="color: #008080;"> 5</span> <span style="color: #0000ff;">function</span> Merge(&<span style="color: #800080;">$arr1</span>, &<span style="color: #800080;">$arr2</span>, <span style="color: #800080;">$s</span>, <span style="color: #800080;">$m</span>, <span style="color: #800080;">$n</span><span style="color: #000000;">) {</span><span style="color: #008080;"> 6</span>     <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$k</span> = <span style="color: #800080;">$s</span>,<span style="color: #800080;">$i</span> = <span style="color: #800080;">$s</span>, <span style="color: #800080;">$j</span> = <span style="color: #800080;">$m</span>+1; <span style="color: #800080;">$i</span> <= <span style="color: #800080;">$m</span> && <span style="color: #800080;">$j</span> <= <span style="color: #800080;">$n</span>; <span style="color: #800080;">$k</span>++<span style="color: #000000;">) {</span><span style="color: #008080;"> 7</span>         <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr1</span>[<span style="color: #800080;">$i</span>]<<span style="color: #800080;">$arr1</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">]) {</span><span style="color: #008080;"> 8</span>             <span style="color: #800080;">$arr2</span>[<span style="color: #800080;">$k</span>] = <span style="color: #800080;">$arr1</span>[<span style="color: #800080;">$i</span>++<span style="color: #000000;">];</span><span style="color: #008080;"> 9</span>         }<span style="color: #0000ff;">else</span><span style="color: #000000;"> {</span><span style="color: #008080;">10</span>             <span style="color: #800080;">$arr2</span>[<span style="color: #800080;">$k</span>] = <span style="color: #800080;">$arr1</span>[<span style="color: #800080;">$j</span>++<span style="color: #000000;">];</span><span style="color: #008080;">11</span> <span style="color: #000000;">        }</span><span style="color: #008080;">12</span> <span style="color: #000000;">    }</span><span style="color: #008080;">13</span>     <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$i</span> <= <span style="color: #800080;">$m</span><span style="color: #000000;">) {</span><span style="color: #008080;">14</span>         <span style="color: #0000ff;">for</span>(; <span style="color: #800080;">$i</span> <= <span style="color: #800080;">$m</span>; <span style="color: #800080;">$i</span>++<span style="color: #000000;">) {</span><span style="color: #008080;">15</span>             <span style="color: #800080;">$arr2</span>[<span style="color: #800080;">$k</span>++] = <span style="color: #800080;">$arr1</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">];</span><span style="color: #008080;">16</span> <span style="color: #000000;">        }</span><span style="color: #008080;">17</span>     } <span style="color: #0000ff;">else</span> <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$j</span> <= <span style="color: #800080;">$n</span><span style="color: #000000;">) {</span><span style="color: #008080;">18</span>         <span style="color: #0000ff;">for</span>(; <span style="color: #800080;">$j</span> <= <span style="color: #800080;">$n</span>; <span style="color: #800080;">$j</span>++<span style="color: #000000;">) {</span><span style="color: #008080;">19</span>             <span style="color: #800080;">$arr2</span>[<span style="color: #800080;">$k</span>++] = <span style="color: #800080;">$arr1</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">];</span><span style="color: #008080;">20</span> <span style="color: #000000;">        }</span><span style="color: #008080;">21</span> <span style="color: #000000;">    }</span><span style="color: #008080;">22</span> <span style="color: #000000;">}</span><span style="color: #008080;">23</span> <span style="color: #008080;">24</span> <span style="color: #008000;">//</span><span style="color: #008000;"> 递归形式的两路归并</span><span style="color: #008080;">25</span> <span style="color: #0000ff;">function</span> MSort(&<span style="color: #800080;">$arr1</span>, &<span style="color: #800080;">$arr2</span>, <span style="color: #800080;">$s</span>, <span style="color: #800080;">$t</span><span style="color: #000000;">) {</span><span style="color: #008080;">26</span>     <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$s</span> == <span style="color: #800080;">$t</span><span style="color: #000000;">) {</span><span style="color: #008080;">27</span>         <span style="color: #800080;">$arr2</span>[<span style="color: #800080;">$s</span>] = <span style="color: #800080;">$arr1</span>[<span style="color: #800080;">$s</span><span style="color: #000000;">];</span><span style="color: #008080;">28</span>     }<span style="color: #0000ff;">else</span><span style="color: #000000;"> {</span><span style="color: #008080;">29</span>         <span style="color: #800080;">$m</span> = <span style="color: #008080;">floor</span>((<span style="color: #800080;">$s</span>+<span style="color: #800080;">$t</span>)/2<span style="color: #000000;">);</span><span style="color: #008080;">30</span>         <span style="color: #800080;">$tmp_arr</span> = <span style="color: #0000ff;">array</span><span style="color: #000000;">();</span><span style="color: #008080;">31</span>         MSort(<span style="color: #800080;">$arr1</span>, <span style="color: #800080;">$tmp_arr</span>, <span style="color: #800080;">$s</span>, <span style="color: #800080;">$m</span><span style="color: #000000;">);</span><span style="color: #008080;">32</span>         MSort(<span style="color: #800080;">$arr1</span>, <span style="color: #800080;">$tmp_arr</span>, <span style="color: #800080;">$m</span>+1, <span style="color: #800080;">$t</span><span style="color: #000000;">);</span><span style="color: #008080;">33</span>         Merge(<span style="color: #800080;">$tmp_arr</span>, <span style="color: #800080;">$arr2</span>, <span style="color: #800080;">$s</span>, <span style="color: #800080;">$m</span>, <span style="color: #800080;">$t</span><span style="color: #000000;">);</span><span style="color: #008080;">34</span> <span style="color: #000000;">    }</span><span style="color: #008080;">35</span> <span style="color: #000000;">}</span><span style="color: #008080;">36</span> <span style="color: #008080;">37</span> <span style="color: #008000;">//</span><span style="color: #008000;"> 对一位数组$arr[0..n-1]中的元素进行两路归并</span><span style="color: #008080;">38</span> <span style="color: #0000ff;">function</span> mergeSort(<span style="color: #800080;">$arr</span><span style="color: #000000;">) {</span><span style="color: #008080;">39</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: #008080;">40</span>     MSort(<span style="color: #800080;">$arr</span>, <span style="color: #800080;">$arr</span>, 0, <span style="color: #800080;">$len</span>-1<span style="color: #000000;">);</span><span style="color: #008080;">41</span>     <span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">;</span><span style="color: #008080;">42</span> }

   使用感

   1. ソート対象のレコード数 n が小さい場合は、直接挿入ソートと単純選択ソートを使用する レコード自体の情報が多い場合は、単純選択ソート方法を使用することをお勧めします。
   2. ソート対象のレコードが基本的にキーワード順の場合は、直接挿入ソートやバブルソートが適しています。
   3. n の値が大きい場合は、クイックソート、ヒープソート、マージソートが使用できます。また、クイックソートは内部ソート方法の中で最も優れた方法であると考えられています。