PHP Hill 정렬 사례 분석

이번에는 PHP Hill 정렬 사례 분석을 가져오겠습니다. PHP Hill 정렬 사례를 사용할 때 주의 사항은 무엇입니까?

기본 아이디어:

힐 정렬은 레코드를 첨자의 특정 증분으로 그룹화하는 것을 의미하며, 각 그룹마다 직접 삽입 정렬이 사용됩니다. 증분이 점차 감소할수록 각 그룹에 더 많은 키워드가 포함됩니다. 그리고 증가량이 1로 줄어들면 전체 시퀀스가 ​​하나의 그룹으로 나뉘고 알고리즘이 종료됩니다.

작업 단계:

먼저 n(시퀀스 레코드 수)보다 작은

integerd1을 첫 번째 증분으로 사용하여 파일의 모든 레코드를 그룹화합니다. 거리가 d1의 배수인 모든 레코드는 동일한 그룹에 배치됩니다. 먼저 각 그룹 내에서 직접 삽입 정렬을 수행한 다음 두 번째 증분 d2

이 방법은 본질적으로 그룹화된 삽입 방법입니다.

멀리 떨어져 있는 숫자를 비교(증분이라고 함)합니다. 이동할 때 여러 요소에 걸쳐 있는 경우 비교[2]를 수행하면 여러 요소 교환이 제거될 수 있습니다. D.L. Shell은 1959년에 그의 이름을 딴 정렬 알고리즘으로 이 아이디어를 구현했습니다. 알고리즘은 먼저 정렬할 숫자 집합을 특정 증분 d에 따라 여러 그룹으로 나누고, 각 그룹에 기록된 첨자는 각 그룹의 모든 요소를 ​​정렬한 다음 더 작은 증분을 사용하여 정렬합니다. 각 그룹 내에서 다시 정렬합니다. 증가량이 1로 감소하면 정렬할 전체 숫자를 하나의 그룹으로 나누어 정렬이 완료됩니다.

일반적으로 처음에는 시퀀스의 절반이 증분으로 사용된 다음 증분이 1이 될 때까지 매번 절반으로 줄어듭니다.

증분 선택 방법에 관해서는 현재까지 최적의 증분 수열을 찾지 못했다고 하는데, 마지막 증분 값이 1과 같아야 한다는 강력한 요구 사항이 있습니다.

특정 인스턴스에 대한 쉘 정렬의 정렬 프로세스

정렬할 파일에 10개의 레코드가 있고 해당 키워드는

49, 38, 65, 97, 76, 13, 27, 49, 55, 04.

증분 시퀀스의 값은 다음과 같습니다.

5, 3, 1

알고리즘 구현:

<?php
//希尔排序(对直接插入排序的改进)
function ShellSort(array &$arr)
{
  $count = count($arr);
  $inc = $count;  //增量
  do {
    //计算增量
    //$inc = floor($inc / 3) + 1;
    $inc = ceil($inc / 2);
    for ($i = $inc; $i < $count; $i++) {
      $temp = $arr[$i];  //设置哨兵
      //需将$temp插入有序增量子表
      for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
        $arr[$j + $inc] = $arr[$j]; //记录后移
      }
      //插入
      $arr[$j + $inc] = $temp;
    }
    //增量为1时停止循环
  } while ($inc > 1);
}
//$arr = array(9,1,5,8,3,7,4,6,2);
$arr = array(49,38,65,97,76,13,27,49,55,04);
ShellSort($arr);
var_dump($arr);

실행 결과:

array(10) {
 [0]=>
 int(4)
 [1]=>
 int(13)
 [2]=>
 int(27)
 [3]=>
 int(38)
 [4]=>
 int(49)
 [5]=>
 int(49)
 [6]=>
 int(55)
 [7]=>
 int(65)
 [8]=>
 int(76)
 [9]=>
 int(97)
}

복잡성 분석:

합격 위 코드 분석을 통해 Hill 정렬의 핵심은 무작위로 그룹화하고 개별적으로 정렬하는 것이 아니라 점프와 같은 결과를 얻기 위해 특정 "증분"으로 분리된 레코드의 하위 시퀀스를 형성하는 것임을 모든 사람이 이미 이해했다고 생각합니다. 이동하므로 정렬 효율성이 높아집니다.

최악의 경우 시간 복잡도는

O(n^2)입니다.

힐 정렬은 불안정한 정렬입니다.

이 기사의 사례를 읽으신 후 방법을 마스터하셨다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트

기타 관련 기사를 주목하세요!

추천 도서:

PHP 빠른 정렬 알고리즘을 사용하는 단계에 대한 자세한 설명

PHP에서 홍보 포스터를 생성하는 단계에 대한 자세한 설명

위 내용은 PHP Hill 정렬 사례 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!