PHP 정렬: PHP 삽입 정렬의 알고리즘 아이디어 및 알고리즘 구현-PHP 튜토리얼-php.cn

PHP 정렬: PHP 삽입 정렬의 알고리즘 아이디어 및 알고리즘 구현

不言

풀어 주다： 2023-04-03 18:56:01

원래의

1524명이 탐색했습니다.

이 기사의 내용은 PHP 정렬에 관한 것입니다. PHP 삽입 정렬의 알고리즘 아이디어와 알고리즘 구현에 대한 내용입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

알고리즘 소개:

여기에서는 "Dahua 데이터 구조"의 예를 사용합니다.

포커는 거의 모든 사람이 플레이해 본 게임입니다. 일반적으로 시작할 때 한 사람이 카드를 주고 나머지는 모두 카드를 뽑아 정렬합니다. 처음 뽑은 카드가 5이고 두 번째 카드가 3이면 자연스럽게 3을 삽입합니다. 5의 앞쪽으로 이동합니다. 카드는 4이고, 3과 5 사이에 있습니다. 네 번째 카드는 6이고, 다섯 번째 카드는 2이고, 3 앞에 삽입합니다. 마지막으로 모든 카드를 뽑았을 때 손에 있는 카드는 작은 것부터 큰 것(포인트)으로 정렬됩니다.

다음 순서를 살펴보겠습니다.

5 3 3 5 // 요소가 하나만 있는 정렬된 목록에 3을 삽입합니다. 5
3 5 4 4 3 5 six 직접 삽입 정렬의 기본 아이디어는 다음과 같습니다. 매번 순서가 지정되지 않은 목록의 요소를 순서가 지정된 목록의 적절한 위치에 삽입하여 순서가 지정된 목록이 순서를 유지하도록 합니다.

첫 번째 패스는 처음 두 숫자를 비교한 다음 두 번째 숫자를 크기에 따라 정렬된 목록에 삽입합니다. 두 번째 패스는 세 번째 데이터와 처음 두 숫자를 뒤에서 앞으로 스캔하고 세 번째 숫자를 정렬된 목록에 삽입합니다. 목록 크기에 따라 순서대로 삽입되며, 전체 정렬 과정은 (n-1) 스캔 후에 완료됩니다.

직접 삽입 정렬은 두 가지 수준의 중첩 루프로 구성됩니다. 외부 루프는 비교할 값을 식별하고 결정합니다. 내부 루프는 비교할 값의 최종 위치를 결정합니다. 직접 삽입 정렬은 비교할 값을 이전 값과 비교하므로 외부 루프는 두 번째 값부터 시작됩니다. 현재 값이 비교될 값보다 크면, 비교될 값보다 작은 값이 발견될 때까지 루프 비교가 계속되고, 비교될 값이 다음 위치에 놓이게 되며 사이클이 종료됩니다.

삽입 정렬의 기본 방법은 모든 레코드가 삽입될 때까지 각 단계에서 정렬할 레코드를 키 크기에 따라 이전에 정렬된 순서의 적절한 위치에 삽입하는 것입니다.

삽입 정렬 알고리즘 구현:

// 直接插入排序
function swap(&$arr,$a,$b)
{
$temp    = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
function insertSort(&$arr)
{
$count = count($arr);
for ($i=1; $i = 0 && $arr[$j] > $temp;$j--) { 
         $arr[$j + 1] = $arr[$j];    //记录后移
    }
    $arr[$j + 1] = $temp;   //插入到正确的位置
} 
}
$arr = array(9,1,5,8,3,7,4,6,2);
insertSort($arr);
var_dump($arr);

로그인 후 복사

실행 결과:

array(9) {

[0]=>
int(1)

[1]=>

int(2)
[2]=> ;
int(3)
[3]=>
int(4)
[4]=>
int(5)
[5]=>
int(6)
[6]=>
int(7)
[7]=>
int(8)
[8]=>
int(9)
}