首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >程序猿修仙之路--算法之插入排序

程序猿修仙之路--算法之插入排序

作者头像
架构师修行之路
发布2019-07-23 16:21:34
3100
发布2019-07-23 16:21:34
举报
文章被收录于专栏:架构师架构师

算法主要衡量标准

1

时间复杂度(运行时间)

在算法时间复杂度维度,我们主要对比较和交换的次数做对比,其他不交换元素的算法,主要会以访问数组的次数的维度做对比。

其实有很多同学对于算法的时间复杂度有点模糊,分不清什么所谓的 O(n),O(nlogn),O(logn)...等,也许下图对一些人有一些更直观的认识。

2

空间复杂度(额外的内存使用)

排序算法的额外内存开销和运行时间同等重要。 就算一个算法时间复杂度比较优秀,空间复杂度非常差,使用的额外内存非常大,菜菜认为它也算不上一个优秀的算法。

3

结果的正确性

这个指标是菜菜自己加上的,我始终认为一个优秀的算法最终得到的结果必须是正确的。就算一个算法拥有非常优秀的时间和空间复杂度,但是结果不正确,又有什么意义呢?

原理

每次在无序的列表中取一个元素插入到一个有序列表的适当位置,成为一个元素加1的新的有序列表。

插入排序根据原理又分为 直接插入排序、二分插入排序、希尔排序等,今天主要讲一下直接插入排序。*直接插入排序是一种稳定的排序算法

假设排序顺序从左至右,具体步骤如下

1

列表第一个元素和前面元素比较,如果小于前面元素(其实不存在),则交换位置。(这步其实可以没有)

2

列表第二个元素和前面元素(第一个元素)比较,如果小于前面元素,则交换位置。

3

列表第三个元素和前面元素(第二个元素)比较,如果小于前面元素,则交换位置。如果和前面元素交换了位置,现在在第二个位置上,则接着继续和前面元素比较(第一个元素),如果小于前面元素,接着再次交换位置,然后再次重复比较过程....

4

继续重复以上过程,直到最后一个元素完成比较

比较移动过程中,如果元素不需要移动意味着该元素排序完毕。

网络上的插入排序大多都是新建一个有序列表用来存放最终结果,其实在无序列表上进行排序操作空间复杂度才更优

❖ 也许一张更直观的图比上千句话效果都好

复杂度

1

时间复杂度

比较次数

对于长度为N的主键不重复的列表,插入排序 平均情况下需要n²/4次比较,最坏情况下需要n²/2次比较,最好的情况下需要n-1 次比较。

交换次数

对于长度为N的主键不重复的列表,插入排序平均情况下需要n²/4次交换,最坏情况下需要n²/2次交换,最好情况下需要0次交换。

性能和特点

总体来说,直接插入排序是一种比较简单的排序算法,很容易理解也很好用代码实现,当然他的特点也很明显:

运行时间和数据初始状态有关

插入排序的思想是把一个元素插入一个有序的列表中,假如这个元素的位置正好是有序部分的末尾呢?也就是说当前元素不用移动位置。

再一次假如整个列表都是有序的会发生什么情况呢?根本就不需要移动任何元素。这也就是为什么在最好的情况下交换次数为0,比较次数为n-1的原因。

假如列表的很大一部分元素是有序的,插入排序可能比大多数排序算法都要快。。

适用场景

直接插入排序对于小型列表或者非随机元素列表很有效。例如:部分元素有序。大体可归纳为:

1

每个元素距离自己的最终位置都不远

2

一个有序的大列表连接一个小列表

3

列表中只有少数元素不正确

其他

为什么插入排序是稳定呢?

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

实现案例

C# 版本

static void Main(string[] args)

{

List<int> data = new List<int>() ;

for (int i = 0; i < 10; i++)

{

data.Add(new Random(Guid.NewGuid().GetHashCode()).Next(1, 100));

}

//打印原始数组值

Console.WriteLine($"原始数据: {string.Join(",", data)}");

int n = data.Count;

//此处可以直接从第二个元素开始

for (int i = 1; i < n; i++)

{

//查找最小的元素的索引

for (int j = i; j>0 ; j--)

{

if (data[j] < data[j - 1])

{

//异或法 交换两个变量,不用临时变量

data[j] = data[j] ^ data[j-1];

data[j-1] = data[j] ^ data[j - 1];

data[j ] = data[j] ^ data[j - 1];

}

}

}

//打印排序后的数组

Console.WriteLine($"排序数据: {string.Join(",", data)}");

Console.Read();

}

运行结果:

原始数据: 72,78,42,60,84,74,60,79,72,52 排序数据: 42,52,60,60,72,72,74,78,79,84

Go版本

家里没环境,还得访问外国网站,以后再补上吧,望见谅。

独乐不如众乐 hehehehehe 我表弟在追学校的一个女生,每天短信无数,可那妞从来都不回他。我对他说:骚年!女人的天性只是八卦和好奇心!就你这样还想泡妞呢!看你表哥的!我用他手机给那妞发:你是我们学校三大美女之一,但我只喜欢你。半分钟之后,那妞就回了:另外两个是谁,你为什么只喜欢我啊?

—END—

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-11-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 架构师修行之路 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
短信
腾讯云短信(Short Message Service,SMS)可为广大企业级用户提供稳定可靠,安全合规的短信触达服务。用户可快速接入,调用 API / SDK 或者通过控制台即可发送,支持发送验证码、通知类短信和营销短信。国内验证短信秒级触达,99%到达率;国际/港澳台短信覆盖全球200+国家/地区,全球多服务站点,稳定可靠。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档