专栏首页决胜机器学习PHP数据结构(十八) ——直接插入排序

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),作者:linhxx

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    PHP数据结构(十二)——静态查找表 (原创内容,转载请注明来源,谢谢) 一、概念 1、查找表:由同一类型数据元素构成的集合。 ...

    用户1327360
  • PHP数据结构(二十) ——其他插入排序

    PHP数据结构(二十)——其他插入排序 (原创内容,转载请注明来源,谢谢) 注:本文是衔接直接插入排序的,因此直接插入排序的相关内容请点击——PHP...

    用户1327360
  • PHP数据结构(二十二) ——快速排序

    PHP数据结构(二十二)——快速排序 (原创内容,转载请注明来源,谢谢) 一、概述 前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行...

    用户1327360
  • 【从0到1学算法】快速排序

    在学习快速排序前,先上开胃菜,快速排序中用到的算法--分而治之(divide and conquer, D&C,分治法)。

    KEN DO EVERTHING
  • 前端排序算法实现

    前端迷
  • Java冒泡排序法升级版

    指尖改变世界
  • JS 插入排序

    插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

    Umbrella1024
  • 堆排序

    function sort_heap(arr){ var temp; var n = arr.length; for(var...

    前朝楚水
  • 重新撸一遍javascript (二)

    key必须是字符串,如果不是js会自动转为字符串,比如对象作为key会转化成 字符串[object Object]

    lilugirl
  • python中对列表元素大小排序(冒泡排序法,选择排序法和插入排序法)—排序算法

    排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个关键字有序的序列。本文主要讲述python...

    zeruns

作者介绍

精选专题

活动推荐

扫码关注云+社区

领取腾讯云代金券