[php]数据结构&算法(PHP描述) 半折插入排序 straight binary sort
1 <?php2 /**
3* 半折插入排序 straight binary sort
4*
5* 原理:当直接插入排序进行到某一趟时，对于 r 来讲，前边 i-1 个记录已经按关键字有序。此时不用直接插入排序的方法，而改为折半查找，找出 r 应插的位置，然后插入。
6 */
7 function sort_binary_insertion($list)
8 {
9 $len=count($list);
10 if(empty($len)) return$list;
11
12 for($i=1; $i<$len; $i++)
13 {
14 $temp=$list[$i];
15 $low=0;
16 $high=$i-1;
17
18 while($low<=$high)
19 {
20 $mid=intval(($low+$high)/2);
21
22 //if($temp > $list[$mid]) // 从大到小
23 if($temp<$list[$mid]) // 从小到大
24 {
25 $high=$mid-1;
26 } else {
27 $low=$mid+1;
28 }
29 }
30 for($j=$i-1; $j>=$mid; $j--)
31 {
32 $list[$j+1] =$list[$j];
33 echoimplode(",",$list),"#mid=",$mid,"<br/>";
34 }
35 $list[$low] =$temp;
36 echoimplode(",",$list),"<br/>";
37 echo"--------------------------------<br/>";
38 }
39
40 return$list;
41 }
42
43
44 $list=array(4,3,2,1,5,7,3,7);
45 $list= sort_binary_insertion($list);
页:
[1]