美文网首页
排序算法-直接插入排序

排序算法-直接插入排序

作者: yulongsun | 来源:发表于2016-09-07 23:15 被阅读17次

1. 算法描述

  1. 第i(1<=i<n)趟,数据序列为{a0,a1,a2...an-1},其前i个元素构成的子序列a{a0,a1...ai-1}是排序的,将元素ai插入到{a0,a1...ai-1}的适当位置,使得插入后的子序列仍然是排序的,a的插入位置由关键字比较决定。
  2. 重复上述操作,n个元素工序n-1趟扫描,每次讲一个元素插入到他前面的子序列中。
直接插入排序过程

2. 代码

3. 时间复杂度

  • 最好情况:序列是已排序序列。O(n)
  • 最坏情况:序列是反向序列。O(n^2)
  • 平均情况: 序列是随机序列。O(n^2)

4. 空间复杂度

  • O(1)

5. 稳定性

  • 稳定

相关文章

  • 排序算法(一)直接插入排序算法

    排序算法(一)直接插入排序算法 1.基本概念  直接插入排序(Straight-Insertion-Sort)是一...

  • 排序

    本文记录几个基础的排序算法。排序算法分为插入排序、交换排序、选择排序等几大类。 插入排序 1. 直接插入排序 O(...

  • 排序——插入排序

    业精于勤荒于嬉 插入排序包括:直接插入排序、折半插入排序、希尔排序(缩小增量排序) 一、直接插入排序 1. 算法思...

  • 插入排序算法实现

    排序算法是最常见,最基础的算法,作者文集中记录了两种排序算法(插入排序,归并排序) 插入排序算法实现很简单直接,附...

  • 经典排序算法-希尔排序Shell sort

    一、希尔排序思想 希尔排序是基于插入排序的快速的排序算法,先分组后对每组进行直接插入排序,再分组再直接执行插入排序...

  • 【数据结构】【C#】013-插入类排序:🥇直接插入排序(稳定)

    插入排序:直接插入排序(稳定) 【 算法思想 】 直接插入排序是一种最基本的插入排序方法,其基本操作是将第 i 个...

  • Java学习记录(常用 算法 排序 )

    排序算法的分类如下: 1.插入排序(直接插入排序、折半插入排序、希尔排序);2.交换排序(冒泡泡排序、快速排序);...

  • 九种排序算法(重要!!)

    分类:(九种排序算法) 1、插入排序:直接插入排序、二分插入排序、希尔排序; 2、选择排序:简单选择排序、堆排序 ...

  • 算法-插入排序

    算 法:插入排序算法时间复杂度: 插入排序算法描述 插入排序伪代码 插入排序实现 插入排序算法概述 插入排...

  • 算法

    1.常用的八个基本排序算法 -前言:希尔排序和直接插入排序属于插入排序算法,简单选择排序和堆排序属于选择排序,冒泡...

网友评论

      本文标题:排序算法-直接插入排序

      本文链接:https://www.haomeiwen.com/subject/ipcsettx.html