PHP数据结构(十八) ——直接插入排序

PHP数据结构(十八)——直接插入排序

(原创内容,转载请注明来源,谢谢)

一、概述

插入排序分为直接插入排序、其他插入排序、希尔排序。其他插入排序又分为折半插入排序、2-路插入排序。

二、直接插入排序

直接插入排序是一种最简单的排序方法,时间复杂度O(n2),实现方式是将一个记录插入到已经排序好的有序表,得到一个新的、记录数增加1的有序表。

插入排序的核心思想,即假设原数组的第0位至第i-1位都是有序排列的(如从小到大),当第i位出现顺序错误(如第i位的值小于第i-1位),则需要进行插入排序。

1、算法

直接插入排序经过以下几步:

1)按照待排序数组的顺序,从第二个数字开始,逐个数字与前一个数字进行比较。

2)假设当前的比较是从小到大的排序,数组arr。当arr[i]>=arr[i-1]时,第i个元素保持原位,对i+1进行比较。

3)当arr[i]<arr[i-1]时,则需要进行插入排序。方法是将arr[i]拎出来,从i-1直至0位置的值,逐个进行比较,当比较到第k位,arr[k]<arr[i]时,将arr[k+1]至arr[i-1]的至分别往后挪一位,挪到arr[k+2]至arr[i]的位置,然后将原来的arr[i]的值插入至arr[k+1]处。再继续往后进行比较。

4)直至遍历完所有的节点,插入排序结束,所得的数组即排序好的数组。

5)当需要从大到小排序时,结果相似,不赘述。

2、关键代码实现如下

         //直接插入排序
         publicfunction directInsertSort(array $arr = array()){
                   //如果没有输入,则拿默认的值比较
                   if(empty($arr)){
                            $arr= $this->arr;
                   }
                   //如果数组为空或者只有一个元素,直接返回原数组
                   if(null== $arr || 1 >= count($arr)){
                            return$arr;
                   }
                   //0...i-1都是有序的,此时插入第i个值
                   for($i=1;$i<count($arr);$i++){
                            //当第i个小于第i-1个时,需要进行插入排序,否则循环下一个数
                            if($arr[$i]< $arr[$i-1]){
                                     //把第i个值往前挪到x位置,保证arr[x-1]<=arr[i],arr[x+1]>arr[i]
                                     $tmp= $arr[$i];
                                      for($j=$i-1;$j>=0&&$arr[$j]>$tmp;$j--){
                                               $arr[$j+1]= $arr[$j];//所有元素往后挪一位
                                     }
                                     //第j+1位赋值留给原来的第i位
                                     $arr[$j+1]= $tmp;
                            }
                   }
                   return$arr;
         }

注:此代码为实现直接插入排序的核心代码,代码的方法写在类中,待全部排序都写完后会有完整版的代码

——written by linhxx 2017.07.16

相关阅读:

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

653
来自专栏数据结构与算法

P1338 末日的传说

题目描述 只要是参加jsoi活动的同学一定都听说过Hanoi塔的传说:三根柱子上的金片每天被移动一次,当所有的金片都被移完之后,世界末日也就随之降临了。 在古老...

2729
来自专栏C语言及其他语言

[每日一题]破解平方数

这次的题目是九月月赛的第二题,相信大家肯定是没问题的 题目描述 给出m个数b1, b2,..., bm,每个数的素数因子都在前t个素数之内,任务是寻找这...

3116
来自专栏JavaQ

HashMap在JDK1.8前后区别精简说

在JDK1.8以前版本中,HashMap的实现是数组+链表,它的缺点是即使哈希函数选择的再好,也很难达到元素百分百均匀分布,而且当HashMap中有大量元素都存...

3247
来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

2665
来自专栏决胜机器学习

PHP数据结构(二十五) ——并归排序

PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

3378
来自专栏小樱的经验随笔

51Nod 1016 水仙花数 V2(组合数学,枚举打表法)

1016 水仙花数 V2 基准时间限制:1 秒 空间限制:131072 KB 分值: 160         难度:6级算法题 水仙花数是指一个 n 位数 ...

2517
来自专栏攻城狮的动态

简谈快速排序

34310
来自专栏计算机视觉与深度学习基础

Leetcode 213 House Robber II

Note: This is an extension of House Robber. After robbing those houses on that...

1848
来自专栏开发技术

排序之堆排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

602

扫描关注云+社区