PHP排序算法系列之插入排序的示例分析-創(chuàng)新互聯(lián)

這篇文章主要介紹了PHP排序算法系列之插入排序的示例分析，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)建站專注于成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)、網(wǎng)站制作、網(wǎng)站開發(fā)。公司秉持“客戶至上,用心服務(wù)”的宗旨,從客戶的利益和觀點(diǎn)出發(fā),讓客戶在網(wǎng)絡(luò)營銷中找到自己的駐足之地。尊重和關(guān)懷每一位客戶，用嚴(yán)謹(jǐn)?shù)膽B(tài)度對待客戶，用專業(yè)的服務(wù)創(chuàng)造價值，成為客戶值得信賴的朋友，為客戶解除后顧之憂。

插入排序

有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外（讓數(shù)組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。

原理

直接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。
設(shè)數(shù)組為a[0…n-1]。

1.初始時，a[0]自成1個有序區(qū)，無序區(qū)為a[1..n-1]。令i=1
2.將a[i]并入當(dāng)前的有序區(qū)a[0…i-1]中形成a[0…i]的有序區(qū)間。
3.i++并重復(fù)第二步直到i==n-1。排序完成。

PHP代碼實(shí)現(xiàn)

function insertSort($arr){
  //獲取需要排序的長度
  $length=count($arr);
  //假定第一個為有序的，所以從$i開始比較
  for ($i=1; $i <$length ; $i++) {
    //存放待比較的值
    $tmp=$arr[$i];
    for($j=$i-1;$j>=0;$j--){
      //若插入值比較小，則將后面的元素后移一位，并將值插入
      if($tmp<$arr[$j]){
        $arr[$j+1]=$arr[$j];
        $arr[$j]=$tmp;
      }else{
        break;
      }
    }
  }
  return $arr;
}

算法時間復(fù)雜度計(jì)算

在好的情況下（元素已經(jīng)排好順序）：那么只需要循環(huán) n-1 次就可以了，時間復(fù)雜度 O（n）
在最差的情況下（元素是逆序的）：要循環(huán)調(diào)整次數(shù)： [ n * (n-1) ] / 2 ，時間復(fù)雜度為 O（n ^ 2）
平均時間復(fù)雜度為：O（n ^ 2）

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“PHP排序算法系列之插入排序的示例分析”這篇文章對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司，，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!

當(dāng)前文章：PHP排序算法系列之插入排序的示例分析-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://muchs.cn/article6/djhsog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、云服務(wù)器、域名注冊、網(wǎng)站策劃、網(wǎng)站維護(hù)、用戶體驗(yàn)

廣告

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