BlueBreeze

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

平均来说插入排序算法复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

下面为代码实现：

<?php
function insert_sort($arr) 
{
	for ($i = 1; $i < count($arr); $i++) 
    {
	     $temp = $arr[$i];
	     for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--)
	     {
			 $arr[$j + 1] = $arr[$j];
			 $arr[$j + 1] = $temp;
	     }
	}
	
	return $arr;
}