PHP sorting algorithm insertion sort

Insert Sort

● The idea of ​​insertion sort:

Consider an unordered array to be sorted as two lists, one in order A list, an unordered list, take out one element to be inserted from the unordered list at a time, and insert it into the ordered list until the unordered list is empty and the sorting is completed

● Actual example :

1. There is an unordered one-dimensional array that needs to be sorted this time. The array is: [36,12,96,-1]

2. First, put the The first element [36] is regarded as an independent ordered list, and the remaining elements [12, 96, -1] are regarded as an unordered list

3. The first The element to be inserted is 12. To insert 12 into an ordered list, you first need to compare 12 and 36. If the inserted element 12 is less than 36, you need to insert 12 in front of 36, that is, 36 must be moved back one Bit.

4. Insertion sort actually requires comparing the total number of array elements minus one round, because the first element does not need to be compared.

$arr = [36,12,96,-1];
//待插入的数
$insertValue = $arr[1];
//待插入数前面的数的索引
$insertIndek = 1 - 1;
//$insertIndek >= 0 保证插入循环时，不越界，保证第一个元素的下标要大于等0
//$insertValue < $arr[$insertIndek] 保证待插入的数还没有找到插入的位置，即待插入的数是小于它前面的那一个元素的
//符合上述条件的，需要将$arr[$insertIndek] 后移
while($insertIndek >= 0 && $insertValue < $arr[$insertIndek]) {
 $arr[$insertIndek+1] = $arr[$insertIndek]; $insertIndek--;
 //代表的就是有序列表的最前面一个元素的前面一个下标 -1；
}
//当退出循环时，代表找到位置 $insertIndek + 1
$arr[$insertIndek + 1] = $insertValue;
//把插入的元素插入到有序列表的第一个位置或者是没发生交换就在本身的位置
$arr = [12,36,96,-1];
//待插入的数
$insertValue = $arr[2];
//待插入数前面的数的索引
$insertIndek = 2 - 1;
//$insertIndek >= 0 保证插入循环时，不越界，保证第一个元素的下标要大于等0
//$insertValue < $arr[$insertIndek] 保证待插入的数还没有找到插入的位置，即待插入的数是小于它前面的那一个元素的
//符合上述条件的，需要将$arr[$insertIndek] 后移
while($insertIndek >= 0 && $insertValue < $arr[$insertIndek]) {
 $arr[$insertIndek+1] = $arr[$insertIndek];
 $insertIndek--;
 //代表的就是有序列表的最前面一个元素的前面一个下标 -1；
}
//当退出循环时，代表找到位置 $insertIndek + 1
$arr[$insertIndek + 1] = $insertValue;//把插入的元素插入到有序列表的第一个位置或者是没发生交换就在本身的位置

And so on to get the completed ordered array

5. The complete code is as follows:

<?php
class InsertSort
{
 public static function insertArraySort(array $data):array
 { 
 if (!is_array($data)) {
 return [&#39;message&#39; => &#39;待排序的序列非数组&#39;];
 }
 $count = count($data);
 if ($count <= 1) {
 return $data;
 }
 for ($i = 1; $i < $count; $i++) {
 //待插入的元素
 $insertValue = $data[$i];
 //待插入数前面的数的索引
 $insertIndek = $i - 1;
 //$insertIndek >= 0 保证插入循环时，不越界，保证第一个元素的下标要大于等0\
 //$insertValue < $arr[$insertIndek] 保证待插入的数还没有找到插入的位置，即待插入的数是小于它前面的那一个元素的
 //符合上述条件的，需要将$arr[$insertIndek] 后移
 while($insertIndek >= 0 && $insertValue < $data[$insertIndek]) {
 $data[$insertIndek+1] = $data[$insertIndek];
 $insertIndek--;//代表的就是有序列表的最前面一个元素的前面一个下标 -1；
 }
 //当退出循环时，代表找到位置 $insertIndek + 1
 //把插入的元素插入到有序列表的第一个位置
 //或者是没发生交换,即待插入元素大于有序列表的最后一个元素，那么这里只需要将有序列表的最后一个元素的索引 + 1,把待插入元素放在后
 //面一位即可
 $data[$insertIndek + 1] = $insertValue;\ }
 return $data;
 }
 }
$arr = [36,12,96,-1];
var_dump(InsertSort::insertArraySort($arr));

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