PHP code example to implement insertion sort

This article brings you code examples about PHP implementation of insertion sort. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

This concludes with regard to the sorting algorithm. Bubble sort, quick sort, selection sort, plus insertion sort in this article, these four algorithms are relatively simple and easy to understand. More complex algorithms will not show off, so as not to mislead others.

Insertion Sort

Insertion Sort (English: Insertion Sort) is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence, finds the corresponding position and inserts it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, the sorted elements need to be repeatedly and gradually shifted backward. , providing insertion space for the latest element.

Generally speaking, insertion sort is implemented on arrays using in-place. The specific algorithm is described as follows:

1. Starting from the first element, the element can be considered to have been sorted.

2. Take out the next element and proceed from backward in the sequence of elements that have been sorted. Pre-scan

3. If the element (sorted) is greater than the new element, move the element to the next position

4. Repeat step 3 until a sorted element is found that is less than or equal to The position of the new element

5. After inserting the new element into the position

6, repeat steps 2~5

Introduction from Wikipedia. The focus is on steps 2~5.

Animation demonstration

#Example

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function insertSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    for ($i = 1; $i < $count; $i++) {
        // 当前值
        $temp = $arr[$i];
        for ($k = $i - 1; $k >= 0; $k--) {
            // 条件成立，比较值后挪一位，将当前值替换成比较值
            // 倒序 $temp > $arr[$k]
            if ($temp  2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )

The above is the detailed content of PHP code example to implement insertion sort. For more information, please follow other related articles on the PHP Chinese website!