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
————广告时间————
马哥教育2017年Python自动化运维开发实战班，马哥联合BAT、豆瓣等一线互联网Python开发达人，根据目前企业需求的Python开发人才进行了深度定制，加入了大量一线互联网公司：大众点评、饿了么、腾讯等生产环境真是项目，课程由浅入深，从Python基础到Python高级，让你融汇贯通Python基础理论，手把手教学让你具备Python自动化开发需要的前端界面开发、Web框架、大监控系统、CMDB系统、认证堡垒机、自动化流程平台六大实战能力，让你从0开始蜕变成Hold住年薪20万的Python自动化开发人才。
扫描二维码领取学习资料
