PHPでの挿入ソート

<code><span><span><?php </span>header(<span>"content-type:text/html;charset=utf-8"</span>);

<span>//直接插入排序实现从小到大排序</span><span>//思路：每一趟排序将待排序的记录(元素)插入到前面的有序数列中，从左到右不断增大有序数列</span><span>//关键：找到前面的有序数列中正确插入位置。</span><span>$arr</span>  =<span>array</span>(<span>6</span>,<span>18</span>,<span>2</span>,<span>4</span>,<span>16</span>,<span>8</span>);

<span>echo</span><span>"<br>排序前:<br>"</span>;
print_r(<span>$arr</span>);

insertSort(<span>$arr</span>);
<span>echo</span><span>"<br>排序后:<br>"</span>;
print_r(<span>$arr</span>);


<span><span>function</span><span>insertSort</span><span>(&<span>$arr</span>)</span>
{</span><span>$len</span> = count(<span>$arr</span>);
  <span>//从第二个记录起，跟前面的有序数列比较寻找插入位置</span><span>for</span>(<span>$i</span> = <span>1</span>;<span>$i</span> $len</span>; <span>$i</span>++)
  {
    <span>$insertData</span> = <span>$arr</span>[<span>$i</span>];<span>//要插入的记录</span><span>$pos</span> = <span>$i</span>;<span>//插入位置</span><span>for</span>(<span>$j</span> = <span>$i</span> - <span>1</span>;<span>$j</span> >= <span>0</span>;<span>$j</span>--)
        {
          <span>if</span>(<span>$arr</span>[<span>$j</span>] > <span>$insertData</span>)<span>//如果前面的记录大于要插入的记录</span>
          {
              <span>$arr</span>[<span>$j</span>+<span>1</span>] = <span>$arr</span>[<span>$j</span>];<span>//前面的记录往后移一个下标</span><span>$pos</span>--;
          }
          <span>else</span>
          {

            <span>break</span>;
          }
        }


     <span>$arr</span>[<span>$pos</span>] = <span>$insertData</span>;<span>//插入到正确位置</span><span>echo</span><span>"<br>第{$i}趟排序结果:"</span>;
     print_r(<span>$arr</span>);

  }



}</span></code>

<code><span><span><?php </span>header(<span>"content-type:text/html;charset=utf-8"</span>);

<span>//二分查找插入排序：跟直接插入排序思路差不多，不同在通过二分查找来确定插入位置</span><span>$arr</span>  =<span>array</span>(<span>6</span>,<span>18</span>,<span>2</span>,<span>4</span>,<span>16</span>,<span>8</span>);

<span>echo</span><span>"<br>排序前:<br>"</span>;
print_r(<span>$arr</span>);

bsInsertSort(<span>$arr</span>);
<span>echo</span><span>"<br>排序后:<br>"</span>;
print_r(<span>$arr</span>);


<span><span>function</span><span>bsInsertSort</span><span>(&<span>$arr</span>)</span>
{</span><span>$len</span> = count(<span>$arr</span>);
  <span>for</span>(<span>$i</span> = <span>1</span>;<span>$i</span> $len</span>; <span>$i</span>++)
  {
     <span>$left</span> = <span>0</span>;
     <span>$right</span> = <span>$i</span> -<span>1</span>;
     <span>$mid</span> = <span>0</span>;
     <span>$insertData</span> = <span>$arr</span>[<span>$i</span>];<span>//要插入的记录</span><span>while</span>(<span>$left</span>$right</span>)
     {
       <span>$mid</span> = (<span>$left</span> + <span>$right</span>)/<span>2</span>;
       <span>if</span>(<span>$insertData</span> > <span>$arr</span>[<span>$mid</span>])
       {
         <span>$left</span> = <span>$mid</span> + <span>1</span>;
       }<span>else</span>
       {
         <span>$right</span> = <span>$mid</span> -<span>1</span>;
       }
     }

     <span>//$left是要插入的位置</span><span>for</span>(<span>$j</span>=<span>$i</span>-<span>1</span>;<span>$j</span>>=<span>$left</span>;<span>$j</span>--)
     {
       <span>$arr</span>[<span>$j</span>+<span>1</span>]  = <span>$arr</span>[<span>$j</span>];<span>//后移比插入记录大的数</span>
     }

     <span>$arr</span>[<span>$left</span>] = <span>$insertData</span>;
  }
}</code>