Detailed explanation of insertion sort in PHP sorting algorithm series

This article mainly introduces the relevant information of insertion sort in the PHP sorting algorithm series to everyone in detail. It has a certain reference value. Interested friends can refer to

insert sort

There is an already ordered data sequence. It is required to insert a number into this already arranged data sequence, but it is required that the data sequence is still ordered after the insertion. In this case, a number must be used. New sorting method - insertion sorting method. The basic operation of insertion sorting is to insert a data into the already sorted ordered data, thereby obtaining a new ordered data with the number plus one. The algorithm is suitable for a small amount of data. The time complexity of data sorting is O(n^2). It is a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array, except for the last element (making the array one more space to have an insertion position), and the second part only contains this one element (i.e. the element to be inserted). After the first part is sorted, this last element is inserted into the sorted first part.

Principle

The basic idea of ​​direct insertion sort (Insertion Sort) is: each time a record to be sorted is inserted into the previously sorted record according to its key size. The appropriate position in the ordered subsequence until all records are inserted.
Suppose the array is a[0...n-1].

1. Initially, a[0] forms an ordered area, and the unordered area is a[1..n-1]. Let i=1
2. Merge a[i] into the current ordered area a[0...i-1] to form an ordered interval of a[0...i].
3.i and repeat the second step until i==n-1. Sorting completed.

PHP code implementation

function insertSort($arr){
  //获取需要排序的长度
  $length=count($arr);
  //假定第一个为有序的，所以从$i开始比较
  for ($i=1; $i <$length ; $i++) {
    //存放待比较的值
    $tmp=$arr[$i];
    for($j=$i-1;$j>=0;$j--){
      //若插入值比较小，则将后面的元素后移一位，并将值插入
      if($tmp<$arr[$j]){
        $arr[$j+1]=$arr[$j];
        $arr[$j]=$tmp;
      }else{
        break;
      }
    }
  }
  return $arr;
}

Algorithm time complexity calculation

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

The above is the entire content of this article, I hope it will be helpful to everyone's learning Help, and I hope everyone will support php Chinese website.

Articles you may be interested in:

Explanation of Bucket Sorting Algorithm in PHP

Detailed explanation of the problems encountered when developing and setting up lazy loading in Laravel Service Provider

PHP implements sorting heap sort algorithm

The above is the detailed content of Detailed explanation of insertion sort in PHP sorting algorithm series. For more information, please follow other related articles on the PHP Chinese website!