집 > 기사 > 백엔드 개발 > PHP 정렬 알고리즘 Shell Sort(쉘 정렬)

PHP 정렬 알고리즘 Shell Sort(쉘 정렬)

不言원래의: 2018-04-20 12:45:261683검색

이 글에서는 주로 PHP 정렬 알고리즘인 Shell Sort를 소개합니다. Shell Sort의 원리, 구현 방법 및 관련 주의 사항을 예제 형식으로 자세히 분석합니다. 도움이 필요한 친구는 이 글의 예제를 참고할 수 있습니다.

PHP 정렬에 대해 설명합니다. 알고리즘 쉘 정렬. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

기본 아이디어:

Hill 정렬은 레코드가 특정 첨자의 증분에 따라 그룹화되고 각 그룹에 대해 직접 삽입 정렬이 사용되는 것을 의미합니다. 증가량이 점차 감소하고 각 그룹에는 점점 더 많은 키워드가 포함됩니다. 증가량이 1로 감소하면 전체 시퀀스가 하나의 그룹으로 나뉘고 알고리즘이 종료됩니다.

작업 단계:

먼저 n(시퀀스 레코드 수)보다 작은 정수 d1을 첫 번째 증분으로 취하고 파일의 모든 레코드를 그룹화합니다. 거리가 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)

입니다.

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

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

PHP 정렬 알고리즘 Shell Sort(쉘 정렬)

관련 기사