插入排序一般分为直接插入排序和二分插入插入排序。

直接插入排序又可以分为前插和后插，不过虽然是这样分，只是寻找地点的方向不一样而已。“前插”就是从头开始找合适的位置，“后插”就是从后面开始找合适的位置。这里我们只讨论“后插”。直接插入排序的思想很简单，开始时，整个数组都是无序的，默认第一个数是排好序的，然后要把第二个数插入到前面，那么就要找到合适的位置插入，从当前数的前一个数$a与当前数$s进行比较，如果此时$a

COPYPHP
function insertSort(&$a){
    $t = count($a);
    for($i=1; $i<$t; $i++){
        $j = $i-1;
        while($j>=0){
            if($a[$j] < $a[$i]){
                break;
            }else{
                $j--;
            }
        }
        //保存当前数据
                $s = $a[$i];
        //将数据向后移动
        for($k=$i; $k>$j+1; $k--){
            $a[$k] = $a[$k-1];
        }
        //将当前的数据放在找到的位置
        $a[$j+1] = $s;21         }
}

还有就是二分插入排序，二分插入排序只不过查找的方式不同而已。每次要插入的值$a[$i]总是与前面已排好序的中间的值$a[$mid]进行比较，如果$a[$i]比较小则在前面的区间继续二分查找，否则在后面的区间。

COPYPHP
function binarySort(&$a){
    $t = count($a);
        
    for($i=1; $i<$t; $i++){
        $left = 0;
        $right = $i;
        while($left <= $right){
            $mid = intval(($left+$right)/2);
            if($a[$mid] > $a[$i]){
                $right = $mid-1;
            }else if($a[$mid] < $a[$i]){
                $left = $mid+1;
            }else{
                break;
            }
        }
        //保存当前数据
        $s = $a[$i];
        //将数据向后移动
        for($k=$i; $k>=$left; $k--){
            $a[$k] = $a[$k-1];
        }
        //将当前的数据放在找到的位置
        $a[$left] = $s;
    }
}

插入排序也是一种简单的排序方式。