主頁 > 知識庫 > PHP排序算法之希爾排序(Shell Sort)實例分析

PHP排序算法之希爾排序(Shell Sort)實例分析

熱門標簽:地圖標注專員怎么樣 上海做外呼線路的通信公司 電話機器人銷售主要負責什么 長沙做地圖標注公司 四川保險智能外呼系統(tǒng)供應(yīng)商 福建銀行智能外呼系統(tǒng)價格 房產(chǎn)中介用的是什么外呼系統(tǒng) 遼寧ai電銷機器人價格 寧波外呼營銷系統(tǒng)

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

基本思想:

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

操作步驟:

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

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

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

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

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

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

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

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

增量序列的取值依次為:

5,3,1

算法實現(xiàn):

?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];  //設(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時停止循環(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);

運行結(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)鍵并不是隨便分組后各自排序,而是將相隔某個“增量”的記錄組成一個子序列,實現(xiàn)跳躍式的移動,使得排序的效率提高。

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

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

本文參考自《大話數(shù)據(jù)結(jié)構(gòu)》,在此僅作記錄,方便以后查閱,大神勿噴!

PS:這里再為大家推薦一款關(guān)于排序的演示工具供大家參考:

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《php排序算法總結(jié)》、《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學運算技巧總結(jié)》

希望本文所述對大家PHP程序設(shè)計有所幫助。

您可能感興趣的文章:
  • PHP排序算法之歸并排序(Merging Sort)實例詳解
  • PHP排序算法之快速排序(Quick Sort)及其優(yōu)化算法詳解
  • PHP排序算法之基數(shù)排序(Radix Sort)實例詳解
  • PHP排序算法之堆排序(Heap Sort)實例詳解
  • PHP排序算法之直接插入排序(Straight Insertion Sort)實例分析
  • PHP排序算法之簡單選擇排序(Simple Selection Sort)實例分析
  • php中sort函數(shù)排序知識點總結(jié)

標簽:延安 常德 深圳 工商登記 澳門 宿遷 宜春 佛山

巨人網(wǎng)絡(luò)通訊聲明:本文標題《PHP排序算法之希爾排序(Shell Sort)實例分析》,本文關(guān)鍵詞  PHP,排序,算法,之,希爾,Shell,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《PHP排序算法之希爾排序(Shell Sort)實例分析》相關(guān)的同類信息!
  • 本頁收集關(guān)于PHP排序算法之希爾排序(Shell Sort)實例分析的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章