思路分析
每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。(从而得到一个新的、个数加一的有序数据)
/*
* 插入排序法
* 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
* */
function insertSort($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默认$array[0]，已经有序，是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是准备插入的数
$insertIndex = $i - 1; //有序表中准备比较的数的下标
while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){
$arr[$insertIndex + 1] = $arr[$insertIndex]; //将数组往后挪
$insertIndex--; //将下标往前挪，准备与前一个进行比较
}
if($insertIndex + 1 !== $i){
$arr[$insertIndex + 1] = $insertVal;
}
}
}
return $arr;
}
function insertSort2($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默认$array[0]，已经有序，是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是准备插入的数
//$j 有序表中准备比较的数的下标
//$j-- 将下标往前挪，准备与前一个进行比较
for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){
$arr[$j+1]= $arr[$j];//将数组往后挪
}
$arr[$j + 1] = $insertVal;
}
}
return $arr;
}
小结：
时间复杂度：O(n^2)
空间复杂度：O(1)
算法适用于少量数据的排序
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
插入排序属于稳定排序
评 论