Detailed Explanation of Insertion Sorting of PHP Sorting Algorithm Series

Insert sort

There is an ordered data sequence, It is required to insert a number into this arranged data sequence, However, it is required that the data sequence is still orderly after insertion, so a new sorting method-insertion sorting method is used at this time. The basic operation of insertion sorting is to insert a data into the ordered data that has been sorted, so as to obtain a new ordered data with the number plus 1. The algorithm is suitable for sorting a small amount of data, and the time complexity is O (n ^ 2). Is a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: Part 1 contains all the elements of the array except the last one (giving the array one more space to insert), while Part 2 contains only this one element (that is, the element to be inserted). After Part 1 is sorted, insert this last element into the ordered Part 1.

Principle

The basic idea of direct insert sorting (Insertion Sort) is to insert one record to be sorted at a time into the appropriate position in the ordered sub-sequence according to its keyword size until all records are inserted.
Let the array be a [0... n-1].

1. At the beginning, a [0] has its own ordered region, and the disordered region is a [1. n-1]. Let i=1
2. a [i] is incorporated into the current ordered region a [0... i-1] to form the ordered interval of a [0... i].
3. i + + and repeat step 2 until i==n-1. Sort complete.

Implementation of PHP code

function insertSort($arr){
  // Gets the length to be sorted 
  $length=count($arr);
  // Assumed number 1 A is orderly, so from $i Start comparing 
  for ($i=1; $i <$length ; $i++) {
    // Store values to be compared 
    $tmp=$arr[$i];
    for($j=$i-1;$j>=0;$j--){
      // If the inserted value is small, the following elements are moved backward 1 Bit and inserts the value into the 
      if($tmp<$arr[$j]){
        $arr[$j+1]=$arr[$j];
        $arr[$j]=$tmp;
      }else{
        break;
      }
    }
  }
  return $arr;
}

Time complexity calculation of algorithm

In the best case (the elements have been ordered): then you only need to loop n-1 times, and the time complexity is O (n)
In the worst case (the elements are in reverse order): the number of times to cycle: [n * (n-1)]/2, the time complexity is O (n ^ 2)
The average time complexity was O (n ^ 2)