一、概述
1、基本思想
对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无须序列。
接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直到最后一个记录插入到有序序列中为止。
2、处理过程
假设有一个数组[1, 17, 27, 16, 15], 目前待排序元素为16,它是第四个元素(下标为3),然后和它前面的元素挨个进行比较:
16 和 27 (下标为2) 进行对比,16 比 27 小,所以元素 27 占据原来 16 的位置(27 的下标从 2 变成 3),将下标 2 的位置空出来,16 占据这个位置。
16 继续和 17 比较,16 比 17 小,下标交换。
16 继续和 1 比较,16 >= 1,所以不交换下标,16 这个元素已经在有序序列中找到了自己的位置。
继续为元素 15 找合适的位置。
二、PHP代码实现
<?php
declare(strict_types = 1);
class TestCase
{
/**
* 插入排序
*
* @param array $array
* @return array
*/
public static function sortArray(array $array) : array
{
$arrayLen = count($array);
for ($i = 1; $i < $arrayLen; $i++) {
$tmp = $array[$i];
for ($k = $i - 1; $k >= 0; $k--) {
if ($tmp < $array[$k]) {
$array[$k + 1] = $array[$k];
$array[$k] = $tmp;
} else {
break;
}
}
}
return $array;
}
}
// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
// 执行排序
$arr = TestCase::sortArray($arr);
// 输出结果
foreach ($arr as $v) {
echo $v . ' ';
}
// 结果
3 15 15 19 20 22 24 36 36 64 77 95