PHP 정렬 알고리즘 삽입 정렬

Insert Sort

● 삽입 정렬의 개념:

순서가 없는 배열을 순서가 있는 목록과 순서가 없는 목록이라는 두 개의 목록으로 정렬한다고 생각하세요. 매번 삽입할 요소를 하나씩 꺼냅니다. 정렬되지 않은 목록이 비어 있고 정렬이 완료될 때까지 정렬된 목록에 삽입하세요

● 실제 예:

1 이번에 정렬해야 할 정렬되지 않은 1차원 배열이 있습니다. 배열은 다음과 같습니다: [36, 12,96,-1]

2 먼저 배열의 첫 번째 요소 [36]을 독립적인 순서 목록으로 처리하고 나머지 요소 [12, 96, -1]을 순서 없는 목록으로 간주합니다

3. 삽입할 첫 번째 요소는 12입니다. 정렬된 목록에 12를 삽입하려면 먼저 12와 36을 비교해야 합니다. 삽입된 요소가 있는 경우 12가 36보다 작은 경우 36 앞에 12를 삽입해야 합니다. 즉, 36을 한 자리 뒤로 이동해야 합니다.

4. 삽입 정렬에서는 실제로 첫 번째 요소를 비교할 필요가 없기 때문에 배열 요소의 총 개수에서 한 라운드를 뺀 비교가 필요합니다.

$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;//把插入的元素插入到有序列表的第一个位置或者是没发生交换就在本身的位置

완성된 배열을 얻기 위한 과정입니다

5. 전체 코드는 다음과 같습니다.

<?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));

위 내용은 PHP 정렬 알고리즘 삽입 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!