這次帶給大家PHP希爾排序案例分析，使用PHP希爾排序案的注意事項有哪些，下面就是實戰案例，一起來看一下。
基本思想：
希爾排序是指記錄按下標的一定增量分組，對每一群組使用直接插入排序，隨著增量逐漸減少，每組包含的關鍵字越來越多，當增量減少至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);</p>
<p style="text-align: left;">運行結果：</p>
<pre class="brush:php;toolbar:false">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希爾排序案例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！
