算法介绍：这里还是借用《大话数据结构》的一个例子：扑克是几乎人人都玩过的游戏。通常我们开局的时候一般都是一个人发牌，其他人同时抽牌和管理牌。如果你抽的第一张牌是5，第二张牌是3，我们自然会插3进去。到5的前面；第三张牌是4，找到3和5之间的中间点；第四张牌是6，放在5之后；第五张牌是2，放在3的前面；...最后，当我们抽完所有的牌后，将我们手中的牌从小到大（点数）排序。让我们看看这个序列：53//将3插入到只有一个元素的有序列表中5354//将4插入到有两个元素的有序列表中353456//将6插入到有序列表中twoelements34534562//insert2intotheorderedlistwithtwoelements345623456直接插入排序的基本思想是：每次从无序中取出第一个元素list并将其插入到有序列表的适当位置，使有序列表仍然是有序的。第一遍比较前两个数，然后根据大小将第二个数插入到有序列表中；第二遍从后向前扫描第三个数据和前两个数，将第三个数按照大小插入到有序列表中；依次进行，经过(n-1)次扫描完成整个排序过程。直接插入排序由两层嵌套循环组成。外层循环识别并确定要比较的值。内层循环确定要比较的值的最终位置。直接插入排序是将要比较的值与其前一个值进行比较，所以外层循环从第二个值开始。当当前值大于待比较值时，继续循环比较，直到找到小于待比较值的值并将待比较值放在下一个位置，循环结束。插入排序的基本方法是：每一步将一条待排序的记录根据其key的大小插入到之前排序好的序列中的合适位置，直到所有记录都被插入。算法实现：//直接插入排序函数swap(&$arr,$a,$b){$temp=$arr[$a];$arr[$a]=$arr[$b];$arr[$b]=$temp;}functioninsertSort(&$arr){$count=count($arr);for($i=1;$i<$count;$i++){$temp=$arr[$i];对于($j=$i-1;$j>=0&&$arr[$j]>$temp;$j--){$arr[$j+1]=$arr[$j];//记录回来}$arr[$j+1]=$temp;//插入到正确的位置}}$arr=array(9,1,5,8,3,7,4,6??,2);insertSort($arr);var_dump($arr);运行结果：array(9){[0]=>int(1)[1]=>int(2)[2]=>int(3)[3]=>整数(4)[4]=>整数(5)[5]=>整数(6)[6]=>整数(7)[7]=>整数(8)[8]=>整数(9)}
