插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插插入到已入,直至整个序列有序为止。

要点:设立哨兵,作为临时存储和判断数组边界之用。

直接插入排序示例:

如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

直接插入排序(straight insertion sort)的做法是:

每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

哨兵的作用



算法中引进的附加记录R[0]称监视哨或哨兵(Sentinel)。

哨兵有两个作用:

① 进人查找(插入位置)循环之前,它保存了R[i]的副本,使不致于因记录后移而丢失R[i]的内容;

② 它的主要作用是:在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0),因为R[0].可以和自己比较,循环判定条件不成立使得查找循环结束,从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

注意:

① 实际上,一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。

【例】单链表中的头结点实际上是一个哨兵

② 引入哨兵后使得测试查找循环条件的时间大约减少了一半,所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法,要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技,而应该深刻理解并掌握这种技巧。

算法的实现:

#include<iostream>
using namespace std;
int main()
{
 int a[]={98,76,109,34,67,190,80,12,14,89,1};
 int k=sizeof(a)/sizeof(a[0]);
 int j;
 for(int i=1;i<k;i++)//循环从第2个元素开始
 {
 if(a[i]<a[i-1])
 {
 int move=a[i];
 for(j=i-1;j>=0 && a[j]>move;j--)//a[j]若小于要挪动的数,则是循环终止的条件
 {
 a[j+1]=a[j];//将a[i]前元素向后挪动一个
 }
 a[j+1]=move;//此处就是a[j+1]=move;
 }
 }
 for(int f=0;f<k;f++)
 {
 cout<<a[f]<<"  ";
 }
 return 0;
}

效率:

时间复杂度:O(n^2).

其他的插入排序有二分插入排序,2-路插入排序。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LanceToBigData

JavaSE(八)之集合概述

前几天其实一直在学习关于linux的内容和kvm虚拟化的知识。今天有时间来回顾一下集合相关的知识,接下来我将带大家一起来回顾一起集合关联的知识。 不要辜负自己花...

1895
来自专栏Coding迪斯尼

面试算法:在未知长度的排序数组中进行快速查找

1152
来自专栏web前端教室

不学不知道,sort()方法中的坑

今天的前端零基础课,在讲到js中的sort()排序方法的时候,说sort()这个方法在给数字排序的时候,根本不是按数字大小来排序的。 它是把数字都当成字符串来看...

19210
来自专栏ACM算法日常

trie树(字典树)-HDU1251

举一个例子,给50000个由小写字母构成的长度不超过10的单词,然后问某个公共前缀是否出现过。如果我们直接从字符串集中从头往后搜,看给定的字符串是否为字符串集中...

2301
来自专栏chenjx85的技术专栏

leetcode-367-Valid Perfect Square

2524
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻OC对象的本质

4075
来自专栏老马说编程

(54) 剖析Collections - 设计模式 / 计算机程序的思维逻辑

上节我们提到,类Collections中大概有两类功能,第一类是对容器接口对象进行操作,第二类是返回一个容器接口对象,上节我们介绍了第一类,本节我们介绍第二类。...

2549
来自专栏软件开发

JavaSE学习总结(八)—— 异常处理(Exception)

一、理解异常及异常处理的概念 异常就是在程序的运行过程中所发生的不正常的事件,它会中断正在运行的程序。 异常不是错误 程序中关键的位置有异常处理,提高程序的稳定...

2339
来自专栏大数据学习笔记

Java程序设计(Java9版):第2章 数据类型与运算符(Data types and Operators)

第2章 数据类型与运算符(Data types and Operators) I think everybody in this country should ...

2635
来自专栏GIS讲堂

面向对象的三个基本特征

封装,也就是把客观事物封装成抽象的类,并且类可以把自己的数据和方法只让可信的类或者对象操作,对不可信的进行信息隐藏。

1933

扫码关注云+社区

领取腾讯云代金券