這篇文章給大家分享的是有關(guān)PHP排序算法中希爾排序Shell Sort的示例分析的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。

成都創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括龍華網(wǎng)站建設(shè)、龍華網(wǎng)站制作、龍華網(wǎng)頁制作以及龍華網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，龍華網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到龍華省份的部分城市，未來相信會繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

基本思想：

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

操作步驟：

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

該方法實(shí)質(zhì)上是一種分組插入方法

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

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

關(guān)于增量的取法，據(jù)說迄今為止還沒有找到一種好的增量序列，不過有一個(gè)強(qiáng)烈的要求是 最后一個(gè)增量值必須等于 1 才行。

給定實(shí)例的shell排序的排序過程

假設(shè)待排序文件有10個(gè)記錄，其關(guān)鍵字分別是：

49，38，65，97，76，13，27，49，55，04。

增量序列的取值依次為：

5，3，1

算法實(shí)現(xiàn)：

<?php
//希爾排序(對直接插入排序的改進(jìn))
function ShellSort(array &$arr)
{
  $count = count($arr);
  $inc = $count;  //增量
  do {
    //計(jì)算增量
    //$inc = floor($inc / 3) + 1;
    $inc = ceil($inc / 2);
    for ($i = $inc; $i < $count; $i++) {
      $temp = $arr[$i];  //設(shè)置哨兵
      //需將$temp插入有序增量子表
      for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
        $arr[$j + $inc] = $arr[$j]; //記錄后移
      }
      //插入
      $arr[$j + $inc] = $temp;
    }
    //增量為1時(shí)停止循環(huán)
  } 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);

運(yùn)行結(jié)果：

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)
}

復(fù)雜度分析：

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

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

希爾排序是不穩(wěn)定排序。

感謝各位的閱讀！關(guān)于“PHP排序算法中希爾排序Shell Sort的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

網(wǎng)站題目：PHP排序算法中希爾排序ShellSort的示例分析-創(chuàng)新互聯(lián)
文章起源：http://m.newbst.com/article18/dceodp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、網(wǎng)站內(nèi)鏈、服務(wù)器托管、網(wǎng)站策劃、建站公司、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)