PHP实现插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，适用于少量数据的排序。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是一个用PHP实现插入排序的示例代码：

<?php
function insertionSort(&$array) {
    $length = count($array);
    for ($i = 1; $i < $length; $i++) {
        $key = $array[$i];
        $j = $i - 1;

        // 将array[0..i-1]中大于key的元素向后移动一位
        while ($j >= 0 && $array[$j] > $key) {
            $array[$j + 1] = $array[$j];
            $j = $j - 1;
        }
        $array[$j + 1] = $key;
    }
}

// 测试插入排序
$array = [12, 11, 13, 5, 6];
echo "未排序数组: \n";
print_r($array);

insertionSort($array);

echo "已排序数组: \n";
print_r($array);
?>

代码解释：

1. 函数定义：
   • function insertionSort(&$array)：定义一个名为insertionSort的函数，参数$array通过引用传递，这样可以直接修改原数组。
2. 获取数组长度：
   • $length = count($array)：获取数组的长度。
3. 外层循环：
   • for ($i = 1; $i < $length; $i++)：从数组的第二个元素开始遍历，因为第一个元素默认是已排序的。
4. 保存当前元素：
   • $key = $array[$i]：将当前元素保存到变量$key中。
   • $j = $i - 1：初始化索引$j为当前元素的前一个索引。
5. 内层循环：
   • while ($j >= 0 && $array[$j] > $key)：在内层循环中，如果$j索引的元素大于$key，则将$j索引的元素向后移动一位。
   • $array[$j + 1] = $array[$j]：将$j索引的元素赋值给$j+1索引的位置。
   • $j = $j - 1：递减$j索引。
6. 插入当前元素：
   • $array[$j + 1] = $key：找到适当的位置后，将$key插入到该位置。
7. 测试：
   • 定义一个数组$array并输出未排序的数组。
   • 调用insertionSort($array)函数进行排序。
   • 输出已排序的数组。

运行结果：

未排序数组: 
Array
(
    [0] => 12
    [1] => 11
    [2] => 13
    [3] => 5
    [4] => 6
)
已排序数组: 
Array
(
    [0] => 5
    [1] => 6
    [2] => 11
    [3] => 12
    [4] => 13
)

这样，通过插入排序算法，数组就被成功排序了。插入排序的时间复杂度为O(n^2)，在数据量较小或基本有序的情况下表现较好。