PHP 정렬 알고리즘 힐 정렬

힐 정렬의 교환 정렬

● 문제 소개:

삽입 정렬에서 배열 요소의 배열이 상대적으로 낙관적이면 삽입 횟수가 상대적으로 적어 효율성이 매우 높습니다. 그러나 정렬할 배열이 다음과 같이 데이터가 너무 무례한 경우가 많습니다. [2,3,4,5,6,7,1] 이 배열에 삽입 정렬을 사용하면 다음과 같습니다. 등장:

1. 1라운드: [2,3,4,5,6,7,7]

2. 2라운드: [2,3,4,5,6,6,7]

3. 3라운드: [2,3,4,5,5,6,7]

4. 4라운드: [2,3,4,4,5,6,7]

5. 2,3,3,4,5,6,7]

6. 라운드 6: [2,2,3,4,5,6,7]

7. 라운드 7: [1 ,2,3, 4,5,6,7]

이것은 가장 낙관적이지 않은 상황이며 시간 낭비입니다. 따라서 일부 전문가는 나중에 이를 연구하고 최적화하여 Hill 정렬을 발명했습니다.

Shell's Sort는 "Diminishing Increment Sort"라고도 알려진 삽입 정렬 유형으로, 직접 삽입 정렬 알고리즘보다 효율적이고 향상된 버전입니다.

Hill 정렬은 불안정한 정렬 알고리즘입니다. 이 방법은 D.L.Shell이 ​​1959년에 제안한 이름을 따서 명명되었습니다.

힐 정렬은 첨자의 특정 증분으로 레코드를 그룹화하고, 증분이 점차 감소함에 따라 각 그룹에 포함되는 키워드가 1로 줄어들 때 직접 삽입 정렬 알고리즘을 사용하여 각 그룹을 정렬하는 것입니다.

전체 파일이 하나의 그룹으로 나누어지면 알고리즘이 종료됩니다

●

배열 예시 설명:

1 예를 들어 [9,6,1,3,0,5.7,2]로 정렬할 배열이 있습니다. , 8,4]

2. 위 배열에는 총 10개의 요소가 있습니다. 처음으로 배열을 10/2 = 5개의 그룹으로 나눈 다음 이를 2개씩 비교하고 크기와 위치를 교환합니다.

<?php
$arr = [9,6,1,3,0, 5,7,2,8,4];
$arr[0] > $arr[5] ? &#39;交换位置,小数交换在前，大数交换在后&#39; : &#39;不交换位置&#39;;
$arr[1] > $arr[6] ? &#39;交换位置,小数交换在前，大数交换在后&#39; : &#39;不交换位置&#39;;
$arr[2] > $arr[7] ? &#39;交换位置,小数交换在前，大数交换在后&#39; : &#39;不交换位置&#39;;
$arr[3] > $arr[8] ? &#39;交换位置,小数交换在前，大数交换在后&#39; : &#39;不交换位置&#39;;
$arr[4] > $arr[9] ? &#39;交换位置,小数交换在前，大数交换在后&#39; : &#39;不交换位置&#39;;
for ($i = 5; $i < 10; $i++) {
     for ($j = $i - 5; $j >= 0; $j-=5) {
         if ($data[$j] > $data[$j+5]) {
         $temp = $data[$j];
         $data[$j] = $data[$j+5];
         $data[$j+5] = $temp; 
         } 
     }
 }

최종 1라운드 결과는 다음과 같습니다. [5,6,1,3,0,9,7,2,8,4]

3 2라운드 비교가 다시 시작됩니다. 이전 1라운드를 기준으로 다시 5/2 = 2개의 그룹으로 나눈 다음 두 그룹의 위치를 ​​바꾸고 크고 작은 손가락을 바꿉니다. 다음과 같습니다.

<?php
$arr = [5,6,1,3,0,9,7,2,8,4];
$arr[0] > $arr[2];//1,5  [1,6,5,3,0,9,7,2,8,4]
$arr[2] > $arr[4];//0,5  [1,6,0,3,5,9,7,2,8,4]
$arr[4] > $arr[6];//5,7  [1,6,0,3,5,9,7,2,8,4]
$arr[6] > $arr[8];//7,8  [1,6,0,3,5,9,7,2,8,4]
$arr[1] > $arr[3];//3,6  [1,3,0,6,5,9,7,2,8,4]
$arr[3] > $arr[5];//6,9  [1,3,0,6,5,9,7,2,8,4]
$arr[5] > $arr[7];//2,9  [1,3,0,6,5,2,7,9,8,4]
$arr[7] > $arr[9];//4,9  [1,3,0,6,5,2,7,4,8,9]
...
for ($i = 2; $i < 10; $i++) {
     for ($j = $i - 2; $j >= 0; $j-=2) {
         if ($data[$j] > $data[$j+2]) {
         $temp = $data[$j];
         $data[$j] = $data[$j+2];
         $data[$j+2] = $temp; 
         } 
     }
 }

최종 결과는 [0,2, 1,3,6,4,7,6,8 ,9]

4. 마지막으로 다시 그룹 비교: 2/2 = 1개 그룹. 즉, 결국 두 개를 비교한 다음 다시 위치를 교환합니다

<?php
$arr = [0,2,1,3,5,4,7,6,8,9];
$arr[0] > $arr[1];//[1,3,0,6,5,2,7,4,8,9]
$arr[1] > $arr[2];//[1,0,3,6,5,2,7,4,8,9]
$arr[2] > $arr[3];//[1,0,3,6,5,2,7,4,8,9]
$arr[3] > $arr[4];//[1,0,3,5,6,2,7,4,8,9]
$arr[4] > $arr[5];//[1,0,3,5,2,6,7,4,8,9]
$arr[5] > $arr[6];//[1,0,3,5,2,6,7,4,8,9]
$arr[6] > $arr[7];//[1,0,3,5,2,6,4,7,8,9]
$arr[7] > $arr[8];//[1,0,3,5,2,6,4,7,8,9]
$arr[8] > $arr[9];//[1,0,3,5,2,6,4,7,8,9]
...
for ($i = 1; $i < 10; $i++) {
     for ($j = $i - 1; $j >= 0; $j-=1) {
         if ($data[$j] > $data[$j+1]) { 
         $temp = $data[$j]; 
         $data[$j] = $data[$j+1];
         $data[$j+1] = $temp;
         }
     }
 }

마지막으로 결과는 다음과 같습니다: [0,1,2,3,4,5,6,7,8, 9]

●

완료 코드는 다음과 같습니다.

<?php
class ShellSort
{
 /*** Notes: 希尔排序之交换法排序
 * User: LiYi\ * Date: 2019/11/12 0012\ * Time: 14:30\ * @param array $data\ * @return array\ */\
 public static function shellSortArray(array $data):array
 {
 if (!is_array($data)) {
 return [&#39;message&#39; => &#39;必须传入数组比较排序&#39;];
 }
 $count = count($data);//得到数组的个数
 //如果数组的个数小于等于1就直接返回
 if ($count <= 1) {return $data;}
 //$gap 是每次减半的分组，直到只可以分为一组结束，在php里面需要注意，两个整数相除，除不尽的情况下，得到的是一个浮点数，不是一个向下
 //取整的的整数，所以在最后判断gap 退出循环的时候，需要判断它 >= 1
 for ($gap = $count / 2; $gap >= 1; $gap /= 2) {
         for ($i = $gap; $i < $count; $i++) {
             for ($j = $i - $gap; $j >= 0; $j-=$gap) {
                 if ($data[$j] > $data[$j+$gap]) {
                 //这个地方是比较第一个数和它的步长做比较，交换也是一样
                 $temp = $data[$j]; 
                 $data[$j] = $data[$j+$gap];
                 $data[$j+$gap] = $temp;
                 }
             }
         }
     }
     return $data;
 }
 public static function validate(array $data)
 {
      if (!is_array($data)) {
      return [&#39;message&#39; => &#39;必须传入数组比较排序&#39;];
     }
 $count = count($data);//得到数组的个数
 //如果数组的个数小于等于1就直接返回
 if ($count <= 1){
 return $data;
 }
 return [$data, $count];
 }
 /**\ * Notes: 希尔排序之移位法排序
 * User: LiYi
 * Date: 2019/11/12 0012
 * Time: 14:29
 * @param array $data
 * @return array*/
 public static function ShellSortMoveArray(array $data)
 {
 $count = count($data);//得到数组总数
 for ($gap = $count / 2; $gap > 0; $gap /= 2) {
 //缩小增量，每次减半
 $gap = floor($gap);
 for ($i = $gap; $i < $count; $i++) {
 // $insertIndex = $i;//待插入元素的下表
 $insertValue = $data[$insertIndex];//待插入元素的值
 echo "insertIndex=$insertIndex" . PHP_EOL;
 echo "insertValue=$insertValue" . PHP_EOL;
 if ($data[$insertIndex] < $data[$insertIndex - $gap]) {
 //判断待插入元素和它步长的元素比较，待插入元素小就进入循环
 //判断是否越界了，第一个元素的下标是要大于等于0的，否则退出循环
 //判断后面的元素比前面的元素小，进入循环，否则退出循环
 while ($insertIndex - $gap >= 0 && $insertValue < $data[$insertIndex - $gap]) {
 //把步长前面的大的值向后移动
 $data[$insertIndex] = $data[$insertIndex - $gap];
 $insertIndex -= $gap;//每循环一次就把带插入的坐标减去补偿\
 } //把带插的小值插入到前面
 $data[$insertIndex] = $insertValue;
 }
 }
 }
 return $data;
 }
 public static function testShellOne(array $data)
 {
 $temp = 0;
 $count = count($data);
 for ($i = 5; $i < $count; $i++) {
 for ($j = $i - 5; $j >= 0; $j-=5) {
 if ($data[$j] > $data[$j+5]) {
 $temp = $data[$j];
 $data[$j] = $data[$j+5];
 $data[$j+5] = $temp;
 }
 }
 }
 for ($i = 2; $i < $count; $i++) {
 for ($j = $i - 2; $j >= 0; $j-=2) {
 if ($data[$j] > $data[$j+2]) {
 $temp = $data[$j];
 $data[$j] = $data[$j+2];
 $data[$j+2] = $temp;
  }
  } 
  }
 for ($i = 1; $i < 10; $i++) {
 for ($j = $i - 1; $j >= 0; $j-=1) {
 if ($data[$j] > $data[$j+1]) {
 $temp = $data[$j];
 $data[$j] = $data[$j+1];
 $data[$j+1] = $temp;
 } 
 }
 }
 var_dump($data);
 }
 }
var_dump(ShellSort::shellSortMoveArray([0 => 9, 1 => 6, 2 => 1, 3 => 3, 4 => 0, 5 => 5, 6 => 7, 7 => 2, 8 => 8, 9 => 4]));
// $gap = 10 / 2 = 5
// $insertIndex  = $i = $gap = 5
// $insertValue = $data[$insertIndex] = $data[5] = 5;
// $data[$insertIndex] < $data[$insertIndex - $gap] == $data[5] < $data[5-5] = $data[0] ==> 5 < 9
// while(5 - 5 >= 0 && 5 < 9) {
//  $data[5] = $data[5-5] = $data[0] = 9
//  $insertIndex -= 5 = 0;
//}
// $data[$insertIndex] = $data[0] = $insertValue = 5
// $i++ = 6;
// $insertIndex  = $i =  6
// $insertValue = $data[$insertIndex] = $data[6] = 7;
// $data[$insertIndex] < $data[$insertIndex - $gap] == $data[6] < $data[6-5] = $data[1] ==> 7 < 6
// $i++ = 7;
// $insertIndex  = $i =  7
// $insertValue = $data[$insertIndex] = $data[7] = 2;
// $data[$insertIndex] < $data[$insertIndex - $gap] == $data[7] < $data[7-5] = $data[2] ==> 2 < 1
// $i++ = 8;
// $insertIndex  = $i =  8
// $insertValue = $data[$insertIndex] = $data[8] = 8;
// $data[$insertIndex] < $data[$insertIndex - $gap] == $data[8] < $data[8-5] = $data[3] ==> 8 < 3
// $i++ = 9;
// $insertIndex  = $i =  9
// $insertValue = $data[$insertIndex] = $data[9] = 4;
// $data[$insertIndex] < $data[$insertIndex - $gap] == $data[9] < $data[9-5] = $data[4] ==> 4 < 0

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