迹忆客 专注技术分享

在插入排序（概念）中简单的提到了表插入排序。我简单的总结了一下，写下这篇文章，有需要的可以参考一下。

表插入排序，顾名思义，借助一个索引表对原表进行插入排序，这样做的好处就是省去了对原来表中元素的移动过程。当然单一的整数数组（仅作为试验用）移动元素也是挺方便的，但是对于结构有些复杂的表来说，要想移动表中的元素那可真真不是一件容易的事情了。举个例子（以下PHP中的二维数组）

$arr = array(
     1=>array("uname"=>'张三','age'=>20,'occu'=>'PHP程序员'),
     2=>array("uname"=>'李四','age'=>27,'occu'=>'PHP程序员'),
     3=>array("uname"=>'赵五','age'=>19,'occu'=>'PHP程序员'),
     4=>array("uname"=>'王六','age'=>33,'occu'=>'PHP程序员'),
     5=>array("uname"=>'刘大','age'=>35,'occu'=>'PHP程序员'),
     6=>array("uname"=>'公子纠','age'=>29,'occu'=>'PHP程序员'),
     7=>array("uname"=>'公子小白','age'=>26,'occu'=>'PHP程序员'),
     8=>array("uname"=>'管仲','age'=>80,'occu'=>'PHP程序员'),
     9=>array("uname"=>'孔丘','age'=>76,'occu'=>'PHP程序员'),
     10=>array("uname"=>'曾子','age'=>66,'occu'=>'PHP程序员'),
     11=>array("uname"=>'子思','age'=>55,'occu'=>'PHP程序员'),
     12=>array("uname"=>'左丘明','age'=>32,'occu'=>'PHP程序员'),
     13=>array("uname"=>'孟子','age'=>75,'occu'=>'PHP程序员'),
     14=>array("uname"=>'宋襄公','age'=>81,'occu'=>'PHP程序员'),
     15=>array("uname"=>'秦穆公','age'=>22,'occu'=>'PHP程序员'),
     16=>array("uname"=>'楚庄王','age'=>45,'occu'=>'PHP程序员'),
     17=>array("uname"=>'赵盾','age'=>58,'occu'=>'PHP程序员'),
     18=>array("uname"=>'廉颇','age'=>18,'occu'=>'PHP程序员'),
     19=>array("uname"=>'蔺相如','age'=>39,'occu'=>'PHP程序员'),
     20=>array("uname"=>'老子','age'=>100,'occu'=>'PHP程序员'),
 );

对于此数组，假如我们只是对age进行排序，但是又不想改变每个元素的位置，这是我们就可以使用表插入排序。借助一个索引表对当前表进行排序。

好了，下面我们开始对表插入排序来分析分析。首先我们需要一张索引表，表结构如下（依然是以php为例）

array(
    index=>array('next'=>值)
)

index 为元素在原来表中的索引

next 指向其下一个索引

举个例子 有以下元素需要排序

我们暂且认为其下标是从1开始的，0位作为开头索引。那么经过排序以后其索引表（称其为B表）如下

接下来我们根据这个例子一步步构造此索引表

第一步：初始化索引表 置其两个元素

第二步： 遍历A表，当前是A表中的第2个元素值为5 。然后从索引表（以后我们都称其为B表）0位的next值开始，依次比较A[$next] 和 5 的大小 终止遍历B表的条件有两个，一是$next为0 二是A[$next] 要大于或者等于5

A[1]大于5 所以对B表做更改 B[0]的next值为2 B[2]的next值为1 如下

$next = B[0][next]    开始为1
while($next 不等于0){
         if(A[$next]<5)
                   $next = B[$next][next]  此时$next值为0
         If(A[$next]>=5)
                   跳出循环
}
If($next等于0 )  //说明直到B表中的最后一个元素仍然没有比5大的元素 则将B[2]的next 值置为0，B[1]的next值置为2 其它的不变
If($next 不等于0) //说明A[$next]值大于等于 5 则将 B[0][next] 置为2 ，B[2][next]置为1

第三步 遍历A表，当前是A表中的第3个元素值为9 。步骤同第二步，这里不再赘述。经过第三步，A、B表如下

B[3][next] = B[2][next]

B[2][next] = 3

第四步：同第二步 A、B表如下

B[4][next] = B[2][next]

B[2][next] = 4

至此索引表的构建方式就已经介绍完了。不知道有没有给大家介绍清楚，如果有不清楚的地方可以在下面留言，看到后我会第一时间回复。

下面我们用PHP实现表插入排序 测试数据就用文章开头的二维数组

$link = array();  //链表
 
   $link[0]=array('next'=>1);//初始化链表  $link第一个元素仅仅作为头部
 $link[1]=array('next'=>0); //将第一个元素放入$link
/*
  * 开始遍历数组 从第二个元素开始
  */
 for($i=2;$i<=count($arr);$i++){
     $p = $arr[$i]; //存储当前待排序的元素
     $index =0;
     $next = 1;  //从开始位置查找链表
     while($next!=0){
         if($arr[$next]['age']<$p['age']){
             $index = $next;
             $next = $link[$next]['next'];
         }
         else break;
     }
     if($next == 0){
         $link[$i]['next'] = 0;
         $link[$index]['next'] = $i;
     }else{
         $link[$i]['next']=$next;
         $link[$index]['next']=$i;
     }
 }

至此索引表已经构建完成，只要遍历此索引表就可以看到我们想要的效果了。下面是输出结果的代码

$next = $link[0]['next'];
while($next!=0){
    print_r($arr[$next]);
    $next = $link[$next]['next'];
}

从以上代码中我们不难看出表插入排序的时间复杂度依然是O(n²)

好了，以上就是所有表插入排序的内容，欢迎大家在下面留言共同讨论，共同提高。