用python实现选择排序算法及优化

上一期是文学,所以这一期该讲技术了,上一次讲到冒泡算法,这次再讲一个同样是用来做排序的算法,选择排序算法。说到算法或数学,很多人会有个误解,觉得在生活中根本没用太明显的实际用途,为了说明数学的重要性,先给大家讲个故事。

子鱼和朋友小A,周末去一家披萨店吃披萨,点了个12寸的。过了一会服务员说:“不好意思,12寸的披萨没有了,给你们换成两个6寸的披萨,可以吗?”这时,小A诧异的回答:“当然不可以,圆的面积是半径的平方乘以π,你该给我们换成4个6寸的。”(12除2的平方*π= 36π,6除2的平方* π = 9π,所以该换成4个)

这时服务员一脸问号:“稍等,我跟我们经理说一下。”

上面这个故事告诉我们数学还是很重要的。

所以接下来进入我们的主题,用python实现选择排序算法及优化,首先理解下排序算法的定义, “选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。”

是不是表示看不懂?看不懂就对了,不然看这文章干嘛。

简单的说,就是有一组数,然后从中选择找出最大的一个,把这个数排到第一个或者最后一个,然后找出第二大的数,排到第二个或者倒数第二个,就这样一直到所有数字都排好为止。

举个栗子,有这样一组数字[1,2,3,4,5,9,8,7,6],然后按下面方式进行排序:

[1,2,3,4,5,9,8,7,6] #原始数列

[9,2,3,4,5,1,8,7,6]#第一次找出最大数9,然后排到第一位

[9,8,3,4,5,1,2,7,6] #第二次找出余下的最大数8,然后排到第二位

[9,8,7,4,5,1,2,3,6] #第二次找出余下的最大数7,然后排到第三位

[9,8,7,6,5,1,2,3,4] #依上面规则逐步递推下去

[9,8,7,6,5,1,2,3,4]

[9,8,7,6,5,4,2,3,1]

[9,8,7,6,5,4,3,2,1]

[9,8,7,6,5,4,3,2,1]

[9,8,7,6,5,4,3,2,1]

明白了原理,接下来用python来实现数学逻辑,代码如下:

到这里是不是觉得就完成了呢?如果觉得是,你就太年轻了。标题都写了优化,所有当然有优化的方法。

接下来就说在python代码中如何优化,既然第一次找到了最大数,那是否能在第一次顺便把最小数也找出来,然后把最小数排到最后去,答案当然是可以啦。

因此,有了以下的优化代码。

到这里是不是觉得就完成了呢?如果觉得是,你还是太年轻了!那还能怎么优化呢?答案是如果经过一轮比较,发现最小值和最大值相等,那就说明实际上剩下的值都是相等的了。于是,有了以下代码。

到这里是不是觉得就完成了呢?如果觉得是,你依然太年轻了!还有是一点能优化的地方,就是发现最小值索引值和最大值的索引值不同,但是值相同的情况,这种情况交换等于无用功。因此可以再加一条判断的。这里就不再提供代码了。不然文章太长了。

今天就到此为止。祝大家周末快乐,端午节快乐!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180615G1KV4800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券