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

yipeiwu_com5年前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)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【宜配屋www.yipeiwu.com】。

相关文章

php 转换字符串编码 iconv与mb_convert_encoding的区别说明

iconv — Convert string to requested character encoding(PHP 4 >= 4.0.5, PHP 5) mb_convert_e...

在PHP中使用Sockets 从Usenet中获取文件

作者:Armel Fauveau  原文地址:http://www.phpbuilder.net/columns/armel20010427.php3 PHP能够打开...

给PHP开发者的编程指南 第一部分降低复杂程度

PHP 是一门自由度很高的编程语言。它是动态语言,对程序员有很大的宽容度。作为 PHP 程序员,要想让你的代码更有效,需要了解不少的规范。很多年来,我读过很多编程方面的书籍,与很多资深程...

PHP进阶学习之类的自动加载机制原理分析

PHP进阶学习之类的自动加载机制原理分析

本文实例讲述了PHP类的自动加载机制。分享给大家供大家参考,具体如下: 前言 我们在常见的PHP的主流框架中通常写好一个类只需写好相应的命名空间或直接实例化类就可以实现类的使用。而不需要...

PHP获取文件的MD5值并判断是否被修改的例子

由于需要判断上传的文件是否被修改过,需要记录上传文件的md5值,这里记录一下获取文件md5值的方法。 复制代码 代码如下: if(isset($_FILES['multimedia'])...