当前位置:Gxlcms > PHP教程 > 排序算法学习之路--表插入排序--迹忆博客

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

时间: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²)

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

人气教程排行