迹忆博客
当前位置: 主页 > 学无止境 > 算法 > 文章

排序算法学习之路——表插入排序

发布时间: 2015-12-23 作者: 迹忆 浏览次数:

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

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

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

迹忆博客——表插入排序图2

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

迹忆博客——表插入排序图3

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

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

迹忆博客——表插入排序图4

第二步:
遍历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  如下

迹忆博客——表插入排序图5

$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

迹忆博客——表插入排序图6

迹忆博客——表插入排序图7

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

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

B[2][next] = 4

迹忆博客——表插入排序图8

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

下面我们用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²)

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

赞助
迹忆博客

除非注明转载,本站文章均为原创,欢迎转载,转载请以链接形式注明出处

本文地址: