php實作希爾排序演算法的方法講解

jacklove
發布: 2023-04-02 19:02:02
原創
1553 人瀏覽過

這篇文章主要介紹了php實現希爾排序演算法的方法,簡單說明了希爾排序的原理,並結合實例形式分析了php實現希爾排序的具體操作技巧,需要的朋友可以參考下

本文實例講述了php實作希爾排序演算法的方法。分享給大家供大家參考,具體如下:

雖然現在各種程式語言都有其各自強大的排序庫函數,但是這些底層實作也都是利用這些基礎或高階的排序演算法。

理解這些複雜的排序演算法還是很有趣的,體會這些排序演算法的精妙~

希爾排序(shell sort):希爾排序是基於插入排序的,差別在於插入排序是相鄰的比較(類似希爾中h=1的情況),而希爾排序是距離h的比較和替換。

希爾排序中一個常數因子n,原始數組被分成各個小組,每個小組由h個元素組成,很可能會有多餘的元素。當然每次循環的時候,h也是遞減的(h=h/n)。第一次循環就是從下標為h開始。希爾排序的一個想法就是,分成小組去排序。

理解這些演算法,最好是有個圖示。就先來代碼吧。

<?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
)
)
*
*/
登入後複製


#您可能感興趣的文章:

# PHP使用自訂key實作對資料加密解密的方法講解

PHP實作的簡單四則運算計算器功能範例講解

Laravel路由中不固定數量的參數如何實現的相關講解

以上是php實作希爾排序演算法的方法講解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板