PHP 插入排序 -- 折半查找

1. 折半查找 -- Binary Insertion Sort

时间复杂度： O(n^2)

适用条件：相对直接插入排序，减少了数值的比较次数。适用于需要排序的数码比较少的情况。

 1 <?php
 2 namespace Test;
 3 
 4 $a = [0 =>3,4,5,1,11,9,27,27,18,20];
 5 
 6 function binaryInsertSort(array &$arr)
 7 {
 8     $guild = 0;  // 监视哨
 9     $arr = array_values($arr);
10     array_unshift($arr,$guild);
11     $len = count($arr);
12 
13     for($i = 2;$i < $len;$i++)
14     {
15         $arr[0] = $arr[$i];
16         $low = 1;
17         $high = $i - 1;
18 
19         while($low <= $high)
20         {
21             $mid = ($high + $low)/2;
22             if($arr[$mid] > $arr[0])
23             {
24                 $high = $mid - 1;
25             }
26             else
27             {
28                 $low = $mid + 1;
29             }
30         }
31 
32         for($j = $i;$j >= $high + 1; --$j)
33         {
34             $arr[$j] = $arr[$j - 1];
35         }
36 
37         $arr[$high + 1] = $arr[0];
38     }
39     array_shift($arr);
40 }
41 
42 binaryInsertSort($a);
43 echo implode(',',$a);

输出：

学习记录，方便复习