PHP排序演算法系列之插入排序的詳解

這篇文章主要為大家詳細介紹了PHP排序演算法系列之插入排序的相關資料，具有一定的參考價值，有興趣的小夥伴們可以參考一下

插入排序

有一個已經有順序的資料序列，要求在這個已經排好的資料序列中插入一個數，但要求插入後此資料序列仍然有序，這個時候就要用到一種新的排序方法－插入排序法,插入排序的基本操作就是將一個資料插入到已經排好序的有序資料中，從而得到一個新的、個數加一的有序數據，演算法適用於少量資料的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入演算法將要排序的陣列分成兩部分：第一部分包含了這個陣列的所有元素，但將最後一個元素除外（讓陣列多一個空間才有插入的位置），而第二部分只包含這一個元素（即待插入元素）。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分。

原理

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

1.初始時，a[0]自成1個有序區，無序區為a[1..n-1]。令i=1
2.將a[i]併入目前的有序區a[0…i-1]中形成a[0…i]的有序區間。
3.i 並重複第二步直到i==n-1。排序完成。

PHP程式碼實作

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

演算法時間複雜度計算

在最好的情況下（元素已經排好順序）：那麼只需要循環n-1 次就可以了，時間複雜度O（n）
在最差的情況下（元素是逆序的）：要循環調整次數： [ n * (n-1 ) ] / 2 ，時間複雜度為O（n ^ 2）
平均時間複雜度為：O（n ^ 2）

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持php中文網。

您可能感興趣的文章:

PHP實作桶排序演算法的講解

關於Laravel Service Provider開發設定延遲載入時遇到的問題詳解

#PHP實作排序堆排序演算法

以上是PHP排序演算法系列之插入排序的詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！