排序算法学习之路--表插入排序--迹忆博客
在插入排序(概念)中简单的提到了表插入排序。我简单的总结了一下,写下这篇文章,有需要的可以参考一下。
表插入排序,顾名思义,借助一个索引表对原表进行插入排序,这样做的好处就是省去了对原来表中元素的移动过程。当然单一的整数数组(仅作为试验用)移动元素也是挺方便的,但是对于结构有些复杂的表来说,要想移动表中的元素那可真真不是一件容易的事情了。举个例子(以下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²)
好了,以上就是所有表插入排序的内容,欢迎大家在下面留言共同讨论,共同提高。

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas



Laravel memudahkan mengendalikan data sesi sementara menggunakan kaedah flash intuitifnya. Ini sesuai untuk memaparkan mesej ringkas, makluman, atau pemberitahuan dalam permohonan anda. Data hanya berterusan untuk permintaan seterusnya secara lalai: $ permintaan-

Pelanjutan URL Pelanggan PHP (CURL) adalah alat yang berkuasa untuk pemaju, membolehkan interaksi lancar dengan pelayan jauh dan API rehat. Dengan memanfaatkan libcurl, perpustakaan pemindahan fail multi-protokol yang dihormati, php curl memudahkan execu yang cekap

Pembalakan PHP adalah penting untuk memantau dan menyahpepijat aplikasi web, serta menangkap peristiwa kritikal, kesilapan, dan tingkah laku runtime. Ia memberikan pandangan yang berharga dalam prestasi sistem, membantu mengenal pasti isu -isu, dan menyokong penyelesaian masalah yang lebih cepat

Laravel menyediakan sintaks simulasi respons HTTP ringkas, memudahkan ujian interaksi HTTP. Pendekatan ini dengan ketara mengurangkan redundansi kod semasa membuat simulasi ujian anda lebih intuitif. Pelaksanaan asas menyediakan pelbagai jenis pintasan jenis tindak balas: Gunakan Illuminate \ Support \ Facades \ http; Http :: palsu ([ 'Google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

Adakah anda ingin memberikan penyelesaian segera, segera kepada masalah yang paling mendesak pelanggan anda? Sembang langsung membolehkan anda mempunyai perbualan masa nyata dengan pelanggan dan menyelesaikan masalah mereka dengan serta-merta. Ia membolehkan anda memberikan perkhidmatan yang lebih pantas kepada adat anda

Artikel membincangkan pengikatan statik lewat (LSB) dalam PHP, yang diperkenalkan dalam Php 5.3, yang membolehkan resolusi runtime kaedah statik memerlukan lebih banyak warisan yang fleksibel. Isu: LSB vs polimorfisme tradisional; Aplikasi Praktikal LSB dan Potensi Perfo

Artikel ini membincangkan menambah fungsi khusus kepada kerangka kerja, memberi tumpuan kepada pemahaman seni bina, mengenal pasti titik lanjutan, dan amalan terbaik untuk integrasi dan debugging.

Alipay Php ...
