PHP排序算法系列之插入排序详解

站长资源 2024/11/28 佚名

2 0 1

插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为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,排序算法,插入排序

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

评论“PHP排序算法系列之插入排序详解”

暂无评论...

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？
根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

2024年11月28日

PHP排序算法系列之插入排序详解

PHP实现桶排序算法

PHP排序算法系列之直接选择排序详解

评论“PHP排序算法系列之插入排序详解”

P70系列延期，华为新旗舰将在下月发布

更新日志

友情链接