php插入排序算法

- PHP语言 - 207 阅 Hot

插入排序

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为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
function insertSort($arr) {
    //区分 哪部分是已经排序好的
    //哪部分是没有排序的
    //找到其中一个需要排序的元素
    //这个元素 就是从第二个元素开始,到最后一个元素都是这个需要排序的元素
    //利用循环就可以标志出来
    //i循环控制 每次需要插入的元素,一旦需要插入的元素控制好了,
    //间接已经将数组分成了2部分,下标小于当前的(左边的),是排序好的序列
    $len=count($arr);
    for ($i=1; $i < $len; $i++) {
        //获得当前需要比较的元素值。
        $tmp = $arr[$i];
        //内层循环控制 比较 并 插入
        for ($j = $i - 1; $j >= 0; $j--) {
            //$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
            if ($tmp < $arr[$j]) {
                //发现插入的元素要小,交换位置
                //将后边的元素与前面的元素互换
                $arr[$j + 1] = $arr[$j];
                //将前面的数设置为 当前需要交换的数
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
                //由于是已经排序好是数组,则前面的就不需要再次比较了。
                break;
            }
        }


    }
    //将这个元素 插入到已经排序好的序列内。
    //返回
    return $arr;
}
$arr = array(88, 1, 2, 5, 3, 66);
$res = insertSort($arr);
print_r($res);
//外循环i=1;内循环j=0;  (1,88,2,5,3,66)
//外循环i=2;内循环j=1;  (1,2,88,5,3,66) 
//外循环i=3;内循环j=2;  (1,2,5,88,3,66) 
//外循环i=4;内循环j=3;  (1,2,5,3,88,66)  (1,2,3,5,88,66)
//外循环i=5;内循环j=4;  (1,2,3,5,66,88)



0 +1

文章来源 " zsl 整理 "

原文地址 " http://www.zsl123.cn/index/info/index/id/44.html "