首页 > 排序算法之直接插入排序

排序算法之直接插入排序

1、基本思想：

       已知待排序列r[1...n],先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成关键字非递减有序序列为止。 具体操作如下：

    （1）查找出r[i]在有序序列r[1...i-1]中的插入位置k;

    （2）将r[k...i-1]中所有元素全部后移一个位置；

    （3）将r[i]复制到r[k],则原r[1...r-1]的有序序列变成了一个r[1...i]的有序序列。

2、直接插入排序算法：

void InsertSort(ElemType A[],int n){int i,j;for(i = 2;i <= n;i++){                   //依次将A[2]~A[n]插入到前面已排序序列if(A[i].key < A[i-1].key){           //若A[i]的关键码小于其前驱，需将A[i]插入有序表A[0] = A[i];                     //复制为哨兵，A[0]不存放元素for(j=i-1;A[0].key

3、性能分析：

     （1）空间复杂度：仅使用了常数个辅助单元，因而空间复杂度为O(1)；

     （2）时间复杂度：①最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n);②最坏情况下，表中元素顺序刚好与排序结果中元素顺序相反时，总的比较次数达到最大，为sum_{i=2}^{n}i，总的移动次数也达到最大，为sum_{i=2}^{n}(i+1);③平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为n²/4。由此，直接插入排序算法的时间复杂度为O(n²)

      （3）直接插入排序是一个稳定的排序方法。

      （4）直接插入排序算法适用于顺序存储和链式存储的线性表。

4、参考文献：

      [1]《数据结构（C语言版）》，严蔚敏、吴伟民编著，清华大学出版社，ISBN：978-7-302-14751-0

      [2]《2019年数据结构考研复习指导》，王道论坛.组编，中国工信出版集团、电子工业出版社，ISBN：978-7-121-33708-6

 

转载于:https://www.cnblogs.com/yzdx/p/10747623.html

更多相关：

  • 原生JS修改html内容不影响绑定的点击事件 请认准insertAdjacentHTML、insertAdjacentText方法

    insertAdjacentText方法与 insertAdjacentHTML方法类似，只不过是插入纯文本，参数相同 参数说明： elementDOM.insertAdjacentHTML(where,html) elementDOM：用于参照插入位置的html元素对象 where：插入位置。包括"beforeBegin"、...

  • oracle与mysql创建表时的区别

    oracle创建表时，不支持在建表时同时增加字段注释。故采用以下方式： #创建表 CREATE TABLE predict_data as (id integer NOT NULL, uid varchar2(80),mid varchar2(8...

  • EXCEL基础篇（二）

    本章主要内容 一、单元格操作 二、插入批注 三、自动求和 四、填充序列 五、查找、替换 六、对齐方式 七、定位 八、插入形状及设置形状 九、页面设置   一单元格操作 1、插入 a、插入单元格    一个单元格选中状态---右击插入（单元左右移）--即可 b、插入单元行/列 c、插入多行单元行/列    选中多行---右击插入----...

  • 剑指offer：面试题31. 栈的压入、弹出序列

    题目：栈的压入、弹出序列 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例 1：...

  • 【高端】几个关于SCSS中for循环的高级玩法

    简单版 @for $i from 1 through 6 {&:nth-of-type(#{$i}) img {transition-delay: calc(0.1 *#{$i}s);//逐次延时效果} } 进阶版 @for $i from 1 through length($数组) {$color: nth($数组, $i);...

  • Gold Code，Gold Sequence

    Gold Code Gold Code是以Robert Gold的名字命名的。它是一组特殊的二进制随机(伪随机)序列，其中成员序列之间的相关性很小。由于这种特性(较小的相关性)，它被广泛地用作各种无线通信系统的扰码。 我们可以非常简单地利用 m序列 来生成Gold Code: 选择两个m序列，且这两个序列的移位寄存器的数量相同，然...

  • LFSR 和 m序列

    翻译自：sharetechnote: LFSR LFSR Linear Feedback Shift Register - 线性反馈移位寄存器 LFSR 是一种移位寄存器电路，其中两个或多个中间步骤的输出线性组合并反馈到输入值，这就是为什么它被称为线性反馈移位寄存器的原因。 该电路具有以下特点: 如果初始状态相同，则最终会得到...

  • leetcode-376 摆动序列

    如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一...

  • C++ Stack Queue priority_queue

    栈stack：stack 后入先出（LIFO） q.top()获取栈顶元素（并不删除）q.pop()删除栈顶元素q.push(x)向栈中加入元素q.empty()判断栈是否为空 队列queue：先入先出（FIFO）   q.front()获取队首元素（并不删除）q.pop()删除队首元素q.push(x)向队列中加入元素q....

  • c++ resizereserve

    resize()，设置大小（size）; reserve()，设置容量（capacity）; size()是分配容器的内存大小，而capacity()只是设置容器容量大小，但并没有真正分配内存。 打个比方：正在建造的一辆公交车，车里面可以设置40个座椅（reserve(40);），这是它的容量，但并不是说它里面就有了40个座椅，只能说...

  • 用v-for循环动态定位坐标显示元素，并遍历元素的left和top坐标位置（只需要用到元素的宽高、索引、每行显示数量）

    v-for="(index,$i) in total" :key="$i":style="{left:`${itemWidth*((index-1)%rowItemCount)}px`,top:`${itemHeight*(Math.ceil(index/rowItemCount)-1)}px`}" //total是显示总数量 //l...

  • 几种经典的居中技巧（垂直和水平居中）

      技巧一（推荐指数★★★★★） 采用top、right、bottom、left，可以不在乎父元素的宽度和高度，对GPU损耗低于技巧三，但是对浏览器内存的消耗高于技巧三 .子元素 {/*父元素需要position: relative|absolute;*/position: absolute;margin: auto;to...

  • leetcode-155 最小栈

    设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。 示例： MinStack minStack = new MinStack(); minStack...

©2024 11GX.COM