时间：2021-07-01 10:21:17 帮助过：20人阅读
表插入排序，顾名思义，借助一个索引表对原表进行插入排序，这样做的好处就是省去了对原来表中元素的移动过程。当然单一的整数数组（仅作为试验用）移动元素也是挺方便的，但是对于结构有些复杂的表来说，要想移动表中的元素那可真真不是一件容易的事情了。举个例子（以下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²)
好了，以上就是所有表插入排序的内容，欢迎大家在下面留言共同讨论，共同提高。