PHP 정렬 알고리즘 직선 삽입 정렬

이 글은 주로 PHP 정렬 알고리즘 중 Straight Insertion Sort를 소개하고 있으며, Straight Insertion Sort 알고리즘의 원리와 구현 기법을 예제 형식으로 자세히 분석하고 있습니다. 도움이 필요한 친구들은 참고할 수 있습니다. PHP 정렬 알고리즘 직선 삽입 정렬을 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

알고리즘 소개: 여기서 "Dahua 데이터 구조"의 예를 사용합니다.

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

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

5 3 3 5 // 요소가 하나만 있는 순서 목록에 3을 삽입합니다. 5

3 5 4 4 // 요소가 두 개인 순서 목록에 4를 삽입합니다. 3 5 3 4 5                                                      // 두 요소가 있는 순서 목록에 6을 삽입합니다. 3 4 5
3 4 5 6       2                        // 삽입 2를 두 요소 3 4 5 6 
2 3 4 5 6

을 사용하여 순서 목록에 추가합니다. 기본 아이디어: 직접 삽입 정렬의 기본 아이디어는: 매번 순서가 없는 목록에서 첫 번째 요소를 꺼내서 순서가 있는 목록의 적절한 위치에 삽입하여 순서가 있는 목록에 여전히 순서가 있도록 하는 것입니다.

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

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

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

알고리즘 구현:

<?php
//直接插入排序
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function InsertSort(array &$arr){
  $count = count($arr);
  //数组中第一个元素作为一个已经存在的有序表
  for($i = 1;$i < $count;$i ++){
    $temp = $arr[$i];   //设置哨兵
    for($j = $i - 1;$j >= 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)
}

직접 삽입 정렬 알고리즘의 시간 복잡도는

O(n^2)

입니다. 직접 삽입 정렬은 안정적인 정렬입니다.

이 기사는 "Dahua 데이터 구조"를 참조했습니다. 나중에 참고할 수 있도록 여기에만 기록했습니다.

관련 추천:

PHP 정렬 알고리즘 - 쉘 정렬

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