插入排序的思想是从未排序的数组中取出一个元素并将其插入到已排序数组的正确位置。这将导致每次迭代后将已排序数组的长度增加 1，并将未排序数组的长度减少 1。
示例:
为了理解插入排序，让我们考虑一下未排序的数组 [23, 1, 10, 5, 2] 并讨论按升序对数组进行排序所采取的每个步骤。在每一遍中，都会从未排序的数组中取出一个元素，并将其插入到已排序数组中的正确位置。
第一遍: array 是未排序的数组，(23) 被插入到已排序的数组中。由于 (23) 是排序数组的第一个元素，并且没有可比较的元素，因此它保持在其位置。
第二遍: (1) 是从未排序的数组中取出并插入到已排序的数组中。与排序数组的所有元素进行比较，发现(23)是唯一大于(1)的数字。 (1) 被插入到已排序的数组中，并且 (23) 的位置在数组中移动一位。这导致排序数组的长度增加一，未排序数组的长度减少一。
第三遍: (10 ) 取自未排序数组，并与已排序数组的所有元素进行比较。 (23) 是排序数组中唯一大于 (10) 的数字。 (10) 被插入到已排序的数组中，并且 (23) 的位置在数组中移动一位。
第四遍:将(5)与排序数组的所有元素进行比较，发现(10)和( 23) 是需要移动一位才能将 (5) 插入到排序数组中的数字。
第五遍: 将 (2) 插入已排序数组、(5)、(10) 和 (23) 移动一位。
插入排序的实现
<?php
// 插入排序函数
function insertionsort(&$Array, $n) {
for($i=0; $i<$n; $i++) {
$curr = $Array[$i];
$j = $i - 1;
while($j >= 0 && $curr < $Array[$j]) {
$Array[$j + 1] = $Array[$j];
$Array[$j] = $curr;
$j = $j - 1;
}
}
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(1, 10, 23, 50, 4, 9, -4);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
insertionsort($MyArray, $n);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
1 10 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
插入排序中如果数组处于相反顺序，则排序所需的时间最长；如果数组已排序，则排序所需的时间最短。
在最坏的情况下，每个元素都会与所有其他元素进行比较。因此，对于 N 个元素，将进行 N² 次比较，因此插入排序的时间复杂度为 θ(N²)。