An example analysis of direct insertion sorting of PHP sorting algorithm of Straight Insertion Sort

In this paper, the direct insertion sorting (Straight Insertion Sort) of PHP sorting algorithm is described as an example. Share it for your reference, as follows:

Algorithm introduction:

Here we still use an example in "Dahua Data Structure":

Poker is a game that almost every one of us has played. Usually, when we start, we deal cards by one person, while others touch cards by one side and manage cards by one side. If the first card you touch is 5 and the second card is 3, naturally we insert 3 into the front of 5; The third card is 4, and find the middle of 3 and 5; The fourth card is 6, put after 5; The fifth card is 2, inserted in front of 3; ... Finally, when we touch all the cards, the cards in our hands are arranged from small to large (points).

Let's look at this order:

5 3//Insert 3 into an ordered table with only 1 element 5
3 5 4//Insert 4 into an ordered table with two elements 3 5
3 4 5 6//Insert 6 into an ordered table with two elements 3 4 5
3 4 5 6 2//Insert 2 into an ordered table with two elements 3 4 5 6
2 3 4 5 6

Basic ideas:

The basic idea of direct insertion sorting is to take out the first element from the unordered table every time and insert it into the appropriate position of the ordered table, so that the ordered table is still ordered.

The first pass compares the first two numbers, and then inserts the second number into the ordered table according to its size; In the second trip, the third data and the first two numbers are scanned from back to front, and the third number is inserted into the ordered table according to its size; Go on in turn, and after (n-1) scanning, the whole sorting process is completed.

Direct insert sorting consists of two nested loops. The outer loop identifies and determines the values to be compared. The inner layer cycle determines its final position for the value to be compared. Direct insert sort compares the value to be compared with its first value, so the outer loop starts with the second value. If the current 1 value is larger than the value to be compared, the cycle comparison will continue until the smaller value is found and the value to be compared is placed at the following 1 position, ending the cycle.

The basic method of insertion sorting is to insert one record to be sorted into the proper position in the previously sorted sequence according to the size of its keyword in each step until all records are inserted.

Algorithm implementation:

<?php
// Direct insert sort 
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function InsertSort(array &$arr){
  $count = count($arr);
  // The first in the array 1 Elements as 1 Existing ordered tables 
  for($i = 1;$i < $count;$i ++){
    $temp = $arr[$i];   // Set up a sentry 
    for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){
      $arr[$j + 1] = $arr[$j];    // Record backward shift 
    }
    $arr[$j + 1] = $temp;   // Insert into the correct position 
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
InsertSort($arr);
var_dump($arr);

Run results:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

The time complexity of direct insertion sorting algorithm is O (n ^ 2).

A direct insert sort is a stable sort.

This article refers to "Dahua Data Structure", which is only recorded here, which is convenient for future reference. Don't spray it!

PS: Here we recommend another demonstration tool about sorting for your reference:

Online animation demonstrates insert/select/bubble/merge/hill/quick sort algorithm process tool:
http://tools.ofstack.com/aideddesign/paixu_ys

For more readers interested in PHP related contents, please check the special topics of this site: Summary of php Sorting Algorithm, Tutorial of PHP Data Structure and Algorithm, Summary of php Programming Algorithm, Summary of php String (string) Usage, Encyclopedia of PHP Array (Array) Operation Skills, Summary of PHP Common Traversal Algorithms and Skills and Summary of PHP Mathematical Operation Skills

I hope this article is helpful to everyone's PHP programming.