常用的排序算法系列
- 常用的排序算法(一)–快速排序(PHP实现)
- 常用的排序算法(二)–插入排序(PHP实现)
- 常用的排序算法(三)–冒泡排序(PHP实现)
- 常用的排序算法(四)–归并排序(PHP实现)
- 常用的排序算法(五)–选择排序以及优化(PHP实现)
插入排序
插入排序是一种逻辑上非常好理解的排序方式，整个排序的核心就是不断在当前已经排好部分数据的数组里，找到合适的位置插入新数据。就像抓扑克牌，抓一张，然后再手里已经部分已经排好序的手牌的找到位置插进去。
举例说明：
首先，常见的取数据方式是，取数组第一位作为开始排序的数据。（取最末尾也可以，但是操作顺序需要调成对称相反的模式）
假设当前需要排序的数组如下，排序原则是从小到大：
ar = [ 34, 5, 5, 555, 5, 4, 14, 5, 88, 89, 54]
我们定义一个数组叫 order[] , 用来表示部分已经排好序的数据，也就像是抓扑克牌的那只手里的牌。最开始的时候，手里是没有牌的， order[] 也就是一个空数组。
现在开始遍历需要排序的数组，也就是开始一张张抽牌，我们把第 i 次从ar数组中抽牌,，抽进来的这个数据叫做 ar[i]。
如果最开始手里没有牌，$order[] 是一个空数组，那么进来的第一个数据，就可以直接放进order[]数组里面。
之后手里就有牌了，需要把新拿的牌和已有的牌一个个对比。因为排序规则是从小到大，那么就只需要遍历order[]数组，找到一个下标位置j，恰好 order[j-1] < 抽进来的数据 <=order[j] , 这时候就把抽进来的数据 ar[i] 插入到 order[k] 的位置即可。
为了方便，我们把已经排好序里对比的数据叫做data , 也就是data = order[j]。那么简化的判断条件就是，抽进来的数据ar[i] <= 已经排好序里对比的数据data
因为是遍历order[]数组，如果这个抽进来的数据 ar[i] ，比 order[j] 数据每一个都大，那么就直接插入到数组末尾就好了。又因为order[j] 是部分已经从小到大排好的数据，所以直接拿order[末尾]来比较就好了。
if( 抽进来的数据ar[i] > order[末尾] ){
// 也就是 `ar[i]` 比 `order[j]` 每一个都大
order[末尾+1] = 抽进来的数据ar[i]
}
至此，整个排序流程就很明晰了，遍历需要排序的数组ar[] , 一个个抽取数据 ar[i]，然后和已部分排序的order[] 对比，一次次按照大小顺序，找到位置插进order[] 数组里 。最后得到的order[] 数组，就是排序的结果。
数组插入的问题
关于插入的部分，还有一个小细节的问题。
现在有一个数组 { a0, a1, … a(j-1), a(j) …a(n) }, 如何在 j 这个位置插入一个数据，使其变成新数组 { a0, a1, … a(j-1), a(x) ,a(j) …a(n) } 呢？
下面提供两种基于数组操作的思路。
通过逐个向后移动来插入
从末尾的 a(n) 开始向前遍历，逐个往后移动一个位置。直到遇到需要插入的位置 j ，这就刚好腾出来了一个空位，这个空位直接放入需要插入的 a(x) 即可。
通过切分再连接来插入
把数组根据位置j拆分成两个部分，前一个是 { a0, a1, … a(j-1)} ，后一个是{ a(j) …a(n) } ，在前一个数组的末尾添加插入的 a(x) ，然后再连接前后两个数组形成一个新数组即可。
看起来这两种操作差不多，但是实际上，通过逐个向后移动来插入会更快一些。因为数组合并的操作，怼人封装成了系统的函数，但本质上也就是一个个数据赋值的过程。
除了基于数组操作，还可以基于链表来实现插入。不过php没有指针变量，但也可以用对象来做一个伪链表。链表还是用C++来写会更好，基于链表的插入，我们下一篇再谈~
PHP代码运行如图：
PHP版本的实现代码如下：
";
echo "
";
$order = insertAr($ar);
echo "
";
echo "
";
echo 'result:';
print_r(json_encode($order));
function insertAr(array $ar, $len = null, $insert_way = 0)
{
if ($len === null) {
$len = sizeof($ar);
}
$order = [];
//fill the order[]
for ($i = 0; $i < $len; $i++) {//i for ar index
echo "
";
print_r(json_encode($order));
$size = sizeof($order);
if ($size == 0 || $ar[$i] >= $order[$size - 1]) {//empty order OR ar[i] is biggest
$order[] = $ar[$i];
} else {//compare one by one
for ($j = 0; $j < $size; $j++) {
if ($ar[$i] <= $order[$j]) {//add into
if ($insert_way == 1) {
cutAdd($order, $j, $ar[$i]);
} else {
moveAdd($order, $j, $ar[$i]);
}
break;
}//end add into
}//end for of order[j]
}//end compare one by one
}//end fill the order[]
return $order;
}
function cutAdd(& $ar, $index, $data)
{
$left = array_slice($ar, 0, $index);
$right = array_slice($ar, $index);
$left[] = $data;
$ar = array_merge($left, $right);
}
function moveAdd(& $ar, $index, $data)
{
$len = sizeof($ar);
$ar[$len] = null;
for ($i = $len - 1; $i >= $index; $i--) {
$ar[$i + 1] = $ar[$i];
}
$ar[$index] = $data;
}
