重温PHP之插入排序

2018-09-18 06:52:02来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

  插入排序基本思路:将数组分为两个区(已排序区和未排序区),假定数组的第一个元素处于已排序区, 第一个元素之后的所有元素都处于未排序部分。排序时用到双层循环,外层循环用于从未排序部分中取出待排序元素,并逐步缩小未排序部分,内层循环用于从已排序部分寻找插入位置(即不断地从已排序部分寻找比待排序元素大的元素), 然后将较大的已排序区的元素后移,后移的最终结果是已排序区元素的最后一个元素占据待排序元素原来的位置,而已排序区中间空出一个位置),最后将待排序元素插入元素后移之后留下的空位。

 1 //插入排序
 2 function insert_sort($arr) {
 3     //获取数组单元个数
 4     $count = count($arr);
 5     //外层循环用于从未排序区域中取出待排序元素
 6     for ($i=1; $i < $count; $i++) {
 7         //获取当前需要插入已排序区域的元素值
 8         $temp = $arr[$i];
 9         //内层循环用于从已排序区域寻找待排序元素的插入位置
10         for ($j=$i-1; $j >= 0; $j--) {
11             //如果$arr[$i]比已排序区域的$arr[$j]小,就后移$arr[$j]
12             if ($temp < $arr[$j]) {        
13                 $arr[$j+1] = $arr[$j];
14                 $arr[$j] = $temp;
15             } else {
16                 //如果$arr[$i]不小于$arr[$j],则对已排序区无需再排序
17                 break;
18             }
19         }
20     }
21     return $arr;
22 }
23 
24 $arr = array(6, 19, 26, 62, 88, 99, 18, 16, 1);
25 var_dump(insert_sort($arr));
  测试结果:
  
  

 


 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:[PHP] 算法-有序数组旋转后寻找最小值的PHP实现

下一篇:ThinkPHP中RBAC权限管理的简单应用