史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念

内部排序和外部排序

根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类:

内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;

外部排序:指的是排序中要对外存储器进行访问的排序过程。

内部排序是排序的基础,在内部排序中,根据排序过程中所依据的原则可以将它们分为5类:插入排序、交换排序、选择排序、归并排序;根据排序过程的时间复杂度来分,可以分为简单排序、先进排序。冒泡排序、简单选择排序、直接插入排序就是简单排序算法。

评价排序算法优劣的标准主要是两条:一是算法的运算量,这主要是通过记录的比较次数和移动次数来反应;另一个是执行算法所需要的附加存储单元的的多少。

2、简单排序之冒泡法Python实现及优化

原理图

2.1、基本实现

2.2、优化实现

思路:如果本轮有交互,就说明顺序不对;如果本轮无交换,说明是目标顺序,直接结束排序。

总结

冒泡法需要数据一轮轮比较。

优化,则可设定一个标记判断此轮是否有数据交换发生,如果没有发生交换,可以结束排序,如果发生交换,继续下一轮排序

最差的排序情况是,初始顺序与目标顺序完全相反,遍历次数1,...,n-1之和n(n-1)/2

最好的排序情况是,初始顺序与目标顺序完全相同,遍历次数n-1

时间复杂度O(n^2)

3、简单排序之选择排序Python实现及优化

选择排序的核心:每一轮比较找到一个极值(最大值或最小值)放到某一端,对剩下的数再找极值,直至比较结束。

原理图

3.1、基本实现

3.2、优化实现——二元选择排序

思路:减少迭代次数,一轮确定2个数,即最大数和最小数。

3.3、等值情况优化

思路:二元选择排序的时候,每一轮可以知道最大值和最小值,如果某一轮最大最小值都一样了,说明剩下的数字都是相等的,直接结束排序。

3.4、等值情况优化进阶

思路:

[1, 1, 1, 1, 1, 1, 1, 1, 2] 这种情况,找到的最小值索引是-2,最大值索引8,上面的代码会交换2次,最小值两个1交换是无用功,所以,增加一个判断。

还可能存在一些特殊情况可以优化,但是都属于特例的优化了,对整个算法的提升有限。

总结

简单选择排序需要数据一轮轮比较,并在每一轮中发现极值

没有办法知道当前轮是否已经达到排序要求,但是可以知道极值是否在目标索引位置上

遍历次数1,...,n-1之和n(n-1)/2

时间复杂度O(n^2)

减少了交换次数,提高了效率,性能略好于冒泡法

作者:mexp 来源:http://me2xp.blog.51cto.com/6716920/1968672


原文发布于微信公众号 - 马哥Linux运维(magedu-Linux)

原文发表时间:2017-10-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

不基于比较的基数排序原理图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

46213
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1082
来自专栏Python专栏

浅尝Python快速排序

1384
来自专栏HTML5学堂

算法之旅 | 选择排序法

HTML5学堂-码匠:数据快速的计算与排序,与前端页面性能有直接的关系。由于排序的算法有很多,在本次“算法系列”的分享当中,我们先从简单易上手的选择排序法开始,...

3325
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-06.总结二维数组,面向对象

1:二维数组(理解) (1)元素是一维数组的数组。 (2)格式: A:数据类型[][] 数组名 = new 数据类型[m][n]; B:数据类型[][]...

2804
来自专栏fangyangcoder

算法导论中的四种基本排序

                                                        by方阳

1212
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

3395
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3425
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

1082
来自专栏take time, save time

你所能用到的数据结构(五)

七、骚年,这就是你的终极速度了吗? 在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算...

2805

扫码关注云+社区

领取腾讯云代金券