JIYIK CN >

Table insertion sort was briefly mentioned in Insertion sort (concept) . I briefly summarized it and wrote this article. You can refer to it if you need it.

Table insertion sort, as the name implies, uses an index table to sort the original table. The advantage of this is that it saves the process of moving the elements in the original table. Of course, it is also convenient to move elements in a single integer array (only for experimental use), but for a table with a complex structure, it is really not an easy task to move elements in the table. For example (the following two-dimensional array in 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程序员'),
 );

For this array, if we only want to sort the age, but do not want to change the position of each element, we can use table insertion sort. Sort the current table with the help of an index table.

Okay, let's start to analyze the table insertion sort. First we need an index table, the table structure is as follows (still using PHP as an example)

array(
    index=>array('next'=>值)
)

index is the index of the element in the original table

next points to the next index

For example, the following elements need to be sorted

We assume that the subscript starts from 1, with 0 as the starting index. Then after sorting, the index table (called table B) is as follows

Next, we construct this index table step by step according to this example

Step 1: Initialize the index table and set its two elements

Step 2: Traverse table A. The current value of the second element in table A is 5. Then start from the next value at position 0 in the index table (hereinafter referred to as table B), and compare A[$next] and 5 in turn. There are two conditions for terminating the traversal of table B: $next is 0 and A[$next] is greater than or equal to 5.

A[1] is greater than 5, so the next value of B[0] is changed to 2 and the next value of B[2] is 1 as follows

$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

The third step is to traverse table A. The current value of the third element in table A is 9. The steps are the same as the second step and will not be repeated here. After the third step, tables A and B are as follows

B[3][next] = B[2][next]

B[2][next] = 3

Step 4: Same as step 2. Tables A and B are as follows

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

B[2][next] = 4

So far, the construction method of the index table has been introduced. I don't know if I have explained it clearly to you. If you have any questions, you can leave a message below and I will reply as soon as I see it.

Next, we use PHP to implement table insertion sorting test data using the two-dimensional array at the beginning of the article.

$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;
     }
 }

At this point, the index table has been built. Just traverse this index table to see the effect we want. The following is the code for the output result

$next = $link[0]['next'];
while($next!=0){
    print_r($arr[$next]);
    $next = $link[$next]['next'];
}

From the above code, we can easily see that the time complexity of table insertion sort is still O(n²)

Well, the above is all the content about table insertion sort. You are welcome to leave a message below to discuss and improve together.