本文實例講述了PHP排序算法之希爾排序(Shell Sort)。分享給大家供大家參考，具體如下：

基本思想：

希爾排序是指記錄按下標的一定增量分組，對每一組使用 直接插入排序 ，隨著增量逐漸減少，每組包含的關鍵字越來越多，當增量減少至 1 時，整個序列恰好被分成一組，算法便終止。

操作步驟：

先取一個小于 n（序列記錄個數） 的整數 d1 作為第一個增量，把文件的全部記錄分組。所有距離為 d1 的倍數的記錄放在同一個組中。先在各組內進行 直接插入排序；然后，取第二個增量 d2 < d1 重復上述的分組和排序，直至所取的增量 dt=1( dt < d(t-1) …< d2 < d1)，即所有記錄放在同一組中進行 直接插入排序 為止.

該方法實質上是一種分組插入方法

比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比[2] 較就可能消除多個元素交換。D.L.shell于1959年在以他名字命名的排序算法中實現了這一思想。算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。

一般的初次取序列的一半為增量，以后每次減半，直到增量為1。

關于增量的取法，據說迄今為止還沒有找到一種最好的增量序列，不過有一個強烈的要求是 最后一個增量值必須等于 1 才行。

給定實例的shell排序的排序過程

假設待排序文件有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)}

復雜度分析：

通過以上代碼的分析，相信大家已經有些明白，希爾排序的關鍵并不是隨便分組后各自排序，而是將相隔某個“增量”的記錄組成一個子序列，實現跳躍式的移動，使得排序的效率提高。

最壞的情況下時間復雜度是 O(n^2)。

希爾排序是不穩定排序。

本文參考自《大話數據結構》，在此僅作記錄，方便以后查閱，大神勿噴！

相關推薦：

PHP排序算法系列之插入排序實例分享

以上就是PHP排序算法之希爾排序(Shell Sort)的詳細內容，更多請關注 其它相關文章！

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