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> $len; <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> $arr[<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> $len; <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> $len-<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> $len; <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> $len; <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> $k; <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> $len, (<span style="color: #800080;">$j</span> + <span style="color: #800080;">$k</span>) $len; <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> $high<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> $j<span style="color: #000000;">) {</span><span style="color: #008080;">13</span>             <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> $j && <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> $j<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> $j && <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] $primary<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> $j<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> $m; <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> $m && <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] $arr[<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> $m && <span style="color: #800080;">$j</span> $n; <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>]$arr1[<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> $m<span style="color: #000000;">) {</span><span style="color: #008080;">14</span>         <span style="color: #0000ff;">for</span>(; <span style="color: #800080;">$i</span> $m; <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> $n<span style="color: #000000;">) {</span><span style="color: #008080;">18</span>         <span style="color: #0000ff;">for</span>(; <span style="color: #800080;">$j</span> $n; <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值较大时，可以采用快速排序、堆排序和归并排序。另外快速排序被认为是内部排序方法中最好的方法。