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

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

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

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

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Explain the concept of a PHP session in simple terms.Explain the concept of a PHP session in simple terms.Apr 26, 2025 am 12:09 AM

PHPsessionstrackuserdataacrossmultiplepagerequestsusingauniqueIDstoredinacookie.Here'showtomanagethemeffectively:1)Startasessionwithsession_start()andstoredatain$_SESSION.2)RegeneratethesessionIDafterloginwithsession_regenerate_id(true)topreventsessi

How do you loop through all the values stored in a PHP session?How do you loop through all the values stored in a PHP session?Apr 26, 2025 am 12:06 AM

In PHP, iterating through session data can be achieved through the following steps: 1. Start the session using session_start(). 2. Iterate through foreach loop through all key-value pairs in the $_SESSION array. 3. When processing complex data structures, use is_array() or is_object() functions and use print_r() to output detailed information. 4. When optimizing traversal, paging can be used to avoid processing large amounts of data at one time. This will help you manage and use PHP session data more efficiently in your actual project.

Explain how to use sessions for user authentication.Explain how to use sessions for user authentication.Apr 26, 2025 am 12:04 AM

The session realizes user authentication through the server-side state management mechanism. 1) Session creation and generation of unique IDs, 2) IDs are passed through cookies, 3) Server stores and accesses session data through IDs, 4) User authentication and status management are realized, improving application security and user experience.

Give an example of how to store a user's name in a PHP session.Give an example of how to store a user's name in a PHP session.Apr 26, 2025 am 12:03 AM

Tostoreauser'snameinaPHPsession,startthesessionwithsession_start(),thenassignthenameto$_SESSION['username'].1)Usesession_start()toinitializethesession.2)Assigntheuser'snameto$_SESSION['username'].Thisallowsyoutoaccessthenameacrossmultiplepages,enhanc

What are some common problems that can cause PHP sessions to fail?What are some common problems that can cause PHP sessions to fail?Apr 25, 2025 am 12:16 AM

Reasons for PHPSession failure include configuration errors, cookie issues, and session expiration. 1. Configuration error: Check and set the correct session.save_path. 2.Cookie problem: Make sure the cookie is set correctly. 3.Session expires: Adjust session.gc_maxlifetime value to extend session time.

How do you debug session-related issues in PHP?How do you debug session-related issues in PHP?Apr 25, 2025 am 12:12 AM

Methods to debug session problems in PHP include: 1. Check whether the session is started correctly; 2. Verify the delivery of the session ID; 3. Check the storage and reading of session data; 4. Check the server configuration. By outputting session ID and data, viewing session file content, etc., you can effectively diagnose and solve session-related problems.

What happens if session_start() is called multiple times?What happens if session_start() is called multiple times?Apr 25, 2025 am 12:06 AM

Multiple calls to session_start() will result in warning messages and possible data overwrites. 1) PHP will issue a warning, prompting that the session has been started. 2) It may cause unexpected overwriting of session data. 3) Use session_status() to check the session status to avoid repeated calls.

How do you configure the session lifetime in PHP?How do you configure the session lifetime in PHP?Apr 25, 2025 am 12:05 AM

Configuring the session lifecycle in PHP can be achieved by setting session.gc_maxlifetime and session.cookie_lifetime. 1) session.gc_maxlifetime controls the survival time of server-side session data, 2) session.cookie_lifetime controls the life cycle of client cookies. When set to 0, the cookie expires when the browser is closed.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use