1. 插入排序介绍
插入排序是一种简单直观的排序算法，它的基本思想是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。直接插入排序是插入排序的一种实现方式，也是最简单的一种。
2. 直接插入排序算法思路
直接插入排序的思路非常简单，具体步骤如下：
2.1 初始化
首先，假设待排序的序列为arr，序列的长度为n。
2.2 从第一个元素开始
将序列的第一个元素视为已排序序列，将第二个元素至第n个元素视为未排序序列。
2.3 插入操作
对于未排序序列中的每一个元素，将其与已排序序列从后往前逐个比较，找到合适的位置插入。
具体操作是，将该元素与已排序序列中的每个元素从后往前进行比较，直到找到一个元素小于或等于该元素，或者已经到达已排序序列的开头位置。然后将该元素插入到该位置的后一个位置上，即将该位置以及其后的元素都后移一位。
function straightInsertionSort($arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$temp = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $temp) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $temp;
}
return $arr;
}
2.4 重复步骤2.3
重复步骤2.3，直到将未排序序列中的所有元素都插入到已排序序列中。
2.5 完成排序
排序结束后，已排序序列中的元素就是原始序列按照从小到大的顺序排列。
3. 算法示例
以下是对序列 [8, 5, 3, 1, 9] 进行直接插入排序的示例：
$arr = [8, 5, 3, 1, 9];
$result = straightInsertionSort($arr);
print_r($result);
输出结果为：
Array
(
[0] => 1
[1] => 3
[2] => 5
[3] => 8
[4] => 9
)
4. 算法分析
直接插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。尽管直接插入排序的时间复杂度较高，但是由于其简单的实现和不占用额外的空间，对于小规模的数据排序是非常合适的。
此外，直接插入排序是稳定的排序算法，即排序前后相等元素的相对顺序保持不变。
5. 总结
直接插入排序是一种简单而实用的排序算法，它适用于小规模的数据排序，同时具有稳定性和原地排序的特点。通过不断将未排序序列中的元素插入到已排序序列中的合适位置，最终达到整个序列有序的效果。
在实际开发中，当需要对规模较小的数据进行排序时，直接插入排序是一个简单而有效的选择，它的实现逻辑清晰，代码量较少，易于理解和调试。