● 問題引入：

在插入排序中，如果數(shù)組元素的排列情況比較樂觀，那么插入的次數(shù)就比較少，那么效率就很高了，可是很多時候，數(shù)據(jù)就是那么的不敬人意，比如如下的一個待 /

排序的數(shù)組：[2,3,4,5,6,7,1]，這個數(shù)組，如果使用插入排序，那么就會發(fā)生如下的樣子：

1. 第一輪:[2,3,4,5,6,7,7]

2. 第二輪:[2,3,4,5,6,6,7]

3. 第三輪:[2,3,4,5,5,6,7]

4. 第四輪:[2,3,4,4,5,6,7]

5. 第五輪:[2,3,3,4,5,6,7]

6. 第六輪:[2,2,3,4,5,6,7]

7. 第七輪:[1,2,3,4,5,6,7]

這樣的就是最不樂觀的情況，很浪費時間，所以，后來就有大神研究了一下，優(yōu)化優(yōu)化，就發(fā)明了希爾排序。

希爾排序 (Shell's Sort) 是插入排序的一種又稱 “縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。

希爾排序是非穩(wěn)定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，

整個文件恰被分成一組，算法便終止

● 數(shù)組實例說明：

1. 比如有一個待排序的數(shù)組 [9,6,1,3,0,5.7,2,8,4]

2. 上面的數(shù)組一共有 10 個元素，它把數(shù)組第一次分為 10/2 = 5 組，然后兩兩比較，大小位置交換：如下：

<?php$arr = [9,6,1,3,0, 5,7,2,8,4];$arr[0] > $arr[5] ? '交換位置,小數(shù)交換在前，大數(shù)交換在后' : '不交換位置';$arr[1] > $arr[6] ? '交換位置,小數(shù)交換在前，大數(shù)交換在后' : '不交換位置';$arr[2] > $arr[7] ? '交換位置,小數(shù)交換在前，大數(shù)交換在后' : '不交換位置';$arr[3] > $arr[8] ? '交換位置,小數(shù)交換在前，大數(shù)交換在后' : '不交換位置';$arr[4] > $arr[9] ? '交換位置,小數(shù)交換在前，大數(shù)交換在后' : '不交換位置';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;          }      } }

最后第一輪得到的結果就是：[5,6,1,3,0,9,7,2,8,4]

3. 第二輪又開始比較，第二輪是在之前第一輪的基礎上，再次分為 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]

● 完整代碼如下：

<?phphtml' target='_blank'>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 ['message' => '必須傳入數(shù)組比較排序']; } $count = count($data);//得到數(shù)組的個數(shù) //如果數(shù)組的個數(shù)小于等于1就直接返回 if ($count <= 1) {return $data;} //$gap 是每次減半的分組，直到只可以分為一組結束，在php里面需要注意，兩個整數(shù)相除，除不盡的情況下，得到的是一個浮點數(shù)，不是一個向下 //取整的的整數(shù)，所以在最后判斷gap 退出循環(huán)的時候，需要判斷它 >= 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]) {                 //這個地方是比較第一個數(shù)和它的步長做比較，交換也是一樣                 $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 ['message' => '必須傳入數(shù)組比較排序'];     } $count = count($data);//得到數(shù)組的個數(shù) //如果數(shù)組的個數(shù)小于等于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);//得到數(shù)組總數(shù) 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]) { //判斷待插入元素和它步長的元素比較，待插入元素小就進入循環(huán) //判斷是否越界了，第一個元素的下標是要大于等于0的，否則退出循環(huán) //判斷后面的元素比前面的元素小，進入循環(huán)，否則退出循環(huán) while ($insertIndex - $gap >= 0 && $insertValue < $data[$insertIndex - $gap]) { //把步長前面的大的值向后移動 $data[$insertIndex] = $data[$insertIndex - $gap]; $insertIndex -= $gap;//每循環(huán)一次就把帶插入的坐標減去補償/ } //把帶插的小值插入到前面 $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 排序算法之希爾排序的詳細內(nèi)容，更多請關注 其它相關文章！

鄭重聲明：本文版權歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。