PHP sorting algorithm series insertion sort example sharing

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

Insertion 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 this data sequence be inserted. Still in order, at this time a new sorting method - insertion sorting method is used. The basic operation of insertion sorting is to insert a data into the sorted ordered data, thereby obtaining a new, individual Number plus one ordered data, the algorithm is suitable for sorting a small amount of data, and the time complexity 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 sorted): 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 loop adjustments: [ n * (n-1) ] / 2, the time complexity is O (n ^ 2)
The average time complexity is: O (n ^ 2)

Related recommendations:

PHP implements bucket sorting algorithm Example sharing

Detailed explanation of PHP sorting algorithm heap sort

PHP simple selection sorting algorithm learning sharing

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