PHP에서 Hill 정렬 알고리즘을 구현하는 방법에 대한 자세한 분석-PHP 튜토리얼-php.cn

PHP에서 Hill 정렬 알고리즘을 구현하는 방법에 대한 자세한 분석

小云云

풀어 주다： 2023-03-17 20:56:01

원래의

1767명이 탐색했습니다.

다양한 프로그래밍 언어에는 이제 자체적으로 강력한 정렬 라이브러리 기능이 있지만 이러한 기본 구현도 이러한 기본 또는 고급 정렬 알고리즘을 사용합니다. 이러한 복잡한 정렬 알고리즘을 이해하는 것은 여전히 매우 흥미롭습니다. 이 기사에서는 주로 Hill 정렬 알고리즘을 PHP에서 구현하는 방법을 소개하고 Hill 정렬의 원리를 간략하게 설명하며 예제 형식으로 Hill 정렬을 구현하는 PHP의 구체적인 작동 기술을 분석합니다. . 친구가 참조할 수 있어야 하며 모든 사람에게 도움이 되기를 바랍니다.

Hill 정렬(쉘 정렬): Hill 정렬은 삽입 정렬을 기반으로 하며, 삽입 정렬은 인접한 정렬을 비교하는 반면(Hill의 h=1인 경우와 유사) Hill 정렬은 거리 h 비교라는 점입니다. 그리고 교체하세요.

Hill 정렬의 상수 인수 n은 원래 배열을 그룹으로 나누고 각 그룹은 h개의 요소로 구성되며 중복 요소가 있을 수 있습니다. 물론, h는 반복될 때마다 감소합니다(h=h/n). 첫 번째 사이클은 인덱스 h부터 시작됩니다. Hill 정렬의 한 가지 아이디어는 그룹으로 나누어 정렬하는 것입니다.

이러한 알고리즘을 이해하려면 다이어그램이 가장 좋습니다. 코드부터 시작해 보겠습니다.

<?php
/**
 * 希尔排序
 */
function shell_sort(array $arr){
  // 将$arr按升序排列
  $len = count($arr);
  $f = 3;// 定义因子
  $h = 1;// 最小为1
  while ($h < $len/$f){
    $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
  }
  while ($h >= 1){ // 将数组变为h有序
    for ($i = $h; $i < $len; $i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键
      for ($j = $i; $j >= $h; $j -= $h){
        if ($arr[$j] < $arr[$j-$h]){
          $temp = $arr[$j];
          $arr[$j] = $arr[$j-$h];
          $arr[$j-$h] = $temp;
        }
        //print_r($arr);echo &#39;<br/>&#39;; // 打开这行注释，可以看到每一步被替换的情形
      }
    }
    $h = intval($h/$f);
  }
  return $arr;
}
$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
$shell = shell_sort($arr);
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($shell);
/**
*
Array
(
[0] => -3
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 6
[6] => 9
[7] => 13
[8] => 14
[9] => 15
[10] => 17
[11] => 20
[12] => 99
)
)
*
*/

로그인 후 복사

다들 배워보셨나요? 서둘러서 한번 시도해 보세요.