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 条评论
登录 后参与评论

相关文章

来自专栏Python自动化测试

python内部函数学习(九)

python提供了很多的内置函数,这些内置的函数在某些情况下,可以起到很大的作用,而不需要专门去写函数实现XX功能,直接使用内置函数就可以实现,下...

973
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版3.5节栈布局之-fomit-frame-pointer编译选项

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

652
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之用两个栈实现队列(九度OJ1512)

题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 输入: 每个输入文件包含一个测试样例。 对于每个测试样例,第一...

1926
来自专栏用户2442861的专栏

C++ STL源码实现以及分析之vector

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

3461
来自专栏云霄雨霁

设计模式----组合模式

1180
来自专栏JavaEdge

(六)-class文件结构1 什么是JVM的“无关性”?2 纵观Class文件结构

2898
来自专栏DannyHoo的专栏

Copy mutableCopy 深拷贝、浅拷贝

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

1153
来自专栏编程思想之异常处理

Java编程思想之通过异常处理错误

1.     异常分为被检查的异常和运行时异常,被检查的异常在编译时被强制要求检查。异常被用来错误报告和错误恢复,但很大一部分都是用作错误报告的。

621
来自专栏琦小虾的Binary

map 学习(上)——C++中 map 的使用

map 学习(上)——C++中 map 的使用 欠下数据结构的债,迟早是要还的…… 最近写毕业论文过程中,需要用到哈希表的数据结构,此外空闲时间在刷 Leetc...

3356
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.5节C风格数据结构内存布局之基本数据类型构成的结构体

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

1281

扫码关注云+社区