PHP 직접 삽입 정렬 사례 분석

php中世界最好的语言원래의: 2018-05-16 15:18:201906검색

이번에는 PHP 직접 삽입 정렬 사례 분석을 가져오겠습니다. PHP 직접 삽입 정렬의 주의사항은 무엇인가요?

알고리즘 소개:

포커는 우리 모두가 해본 게임입니다. 일반적으로 시작할 때 한 사람이 카드를 주고 나머지는 모두 카드를 뽑아 정렬합니다. 처음 뽑은 카드가 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)입니다.

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

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!