排序算法学习之路--表插入排序--迹忆博客

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

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

$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

$p = $arr [ $i ]; //存储当前待排序的元素

$index =0;

$next = 1;  //从开始位置查找链表

while ( $next !=0){

if ( $arr [ $next ]['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²)

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