PHP排序算法系列之插入排序详解
发布:smiling 来源: PHP粉丝网 添加日期:2021-08-27 10:28:14 浏览: 评论:0
这篇文章主要为大家详细介绍了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)
Tags: PHP排序算法 PHP插入排序
- 上一篇:PHP排序算法系列之直接选择排序详解
- 下一篇:PHP实现桶排序算法
相关文章
- ·PHP中实现冒泡排序和快速排序算法示例(2015-04-04)
- ·PHP 冒泡/快速/选择/插入排序算法实例讲解(2015-12-24)
- ·php四种基础排序算法的运行时间比较(2016-08-25)
- ·php实现的常见排序算法汇总(2021-04-11)
- ·PHP简单选择排序算法实例(2021-05-09)
- ·PHP四种基本排序算法示例(2021-05-22)
- ·PHP版本常用的排序算法汇总(2021-06-30)
- ·PHP排序算法系列之桶排序详解(2021-08-26)
- ·PHP排序算法系列之归并排序详解(2021-08-27)
- ·PHP排序算法系列之直接选择排序详解(2021-08-27)
- ·PHP排序算法之冒泡排序(Bubble Sort)实现方法详解(2021-09-11)
- ·PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析(2021-09-11)
- ·PHP排序算法之基数排序(Radix Sort)实例详解(2021-09-11)
- ·PHP排序算法之快速排序(Quick Sort)及其优化算法详解(2021-09-11)
- ·php 插入排序程序代码(2015-04-13)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)