插入排序

插入排序

function insertSort($arr){
        $n = 0;//起始位置
        for($i= $n + 1;$i<count($arr);$i++){
                $tmp=$arr[$i];
                $key=$i-1;
                while($key>= $n && $tmp<$arr[$key]){
                        $arr[$key+1]=$arr[$key];
                        $key--;
                }
                if(($key+1)!=$i)
                        $arr[$key+1]=$tmp;
        }
        return $arr;
}

代码说明：

第一元素已经是排好了序。（已经是有序序列了，这点很重要）

从第二个元素起，依次与前一个元素比较（当前值（暂存值）跟一个有序的序列比较），比较到直到不需要继续比较，否则比较到首个元素，如果前一个元素大于暂存值，前一个元素占到当前指针key的后一个位置。

执行过while,如果进入while,则$key+1 != $i  成立, 将暂存值放到 $key+1的位置，

                   如果不进入while,则$key+1 等于 $i , 说明 暂存值不需要替换，直接进行下个元素的比较。

插入排序

原文：http://rhino.blog.51cto.com/5504750/1904552