钛节点

排序篇之直接插入排序

发表@2018-09-13 09:15:21

更新@2023-01-21 22:47:40

##### “很多年以后，奥雷连诺上校站在行刑队面前，准会想起父亲带他去参观冰块的那个遥远的下午。”  ------ 节选自西亚·马尔克斯《百年孤独》

当一个泥腿子出身的码了三年的php的phper头一次来到BAT面试的时候，似乎听到看到人家都在用O(n)、O(n^2)抑或AVL、B+Tree、Huffuman之类的词语彼此交流。我能想象出来，在面对面试官的时候，瑟瑟发抖的你被对方的知识体系所笼罩，对方在向你展示冰块，而你，也真是第一次见到冰块。

![](https://ti-node.com/static/upload/6401436212493549568)

不过，话说回来，咱老李也不是个孬种，就算咱老李是编筐专业毕业的，到头来不照样带兵干仗？

![](https://ti-node.com/static/upload/6401437735126564864)

话再说回来，即便是科班的，也有暂七师不是？

![](https://ti-node.com/static/upload/6401438443213160448)

不过，涨涨见识总归还是不错的。一个冒泡排序和一个选择排序，能够初步给你揭开算法的奥妙和重要。王老师是把你带进门了，至于后面怎么着，全看你自己的造化了。

对于直接插入排序，实际上我一直怀疑就是一个程序员在打扑克的时候发明的，因为这整个逻辑过程类似于抽牌。你跟丁伟、老赵玩斗地主，你抽到牌有♥️4、♠️9、♣️6、♣️10、♦️1，作为处女座的你，看到这样一副凌乱的牌自然心里是极不舒服的，所以你决定操作操作一波儿规整一下牌，你看了看9，比4小，不用管了，看到了6，放到4和9中间，看到10，不用动，最后拿1，直接放到了4前面，于是牌变成了♦️1、♥️4、♣️6、♠️9、♣️10，心里终于舒服了。

抽象思维归抽象思维，每次运用到实践上，总是写不出来，发愁。所以为了加深理解，还是老套路，乖乖地纸笔演练吧：
![](https://ti-node.com/static/upload/6401467285353005057)

```php
<?php
$arr = [ 6, 4, 7, 2, 9, 8, 1 ];
$length = count( $arr );
for( $outer = 1; $outer < $length; $outer++ ){
  if( $arr[ $outer ] < $arr[ $outer - 1 ] ){
    $temp = $arr[ $outer ];  
    for( $inner = $outer - 1; $inner >= 0 && $arr[ $inner ] > $temp; $inner-- ){
      $arr[ $inner + 1 ] = $arr[ $inner ];
    }   
    $arr[ $inner + 1 ] = $temp;
  }
}
print_r( $arr );
```
运行结果如下图所示：

![](https://ti-node.com/static/upload/6401467678069882881)

最后，咱旅长心疼咱老李，送了咱一张直接插入排序的动态图，你们感受一下：

![](https://ti-node.com/static/upload/6401468341294202881)