在将排序之前，首先思考一个问题：选择排序、插入排序、冒泡排序的时间复杂度均为 o(n) ，为什么大家在讲排序的时候首先更愿意讲插入排序？
在分析一个排序算法好坏的时候，往往要考虑这么几个方面：
1.时间复杂度
考虑到时间复杂度的时候就要考虑到最好情况和最坏情况，尽可能多的有序当然是最好的情况，完全逆序则是最坏的情况，有序度不同，算法的性能也不同。
2.空间复杂度
算法的内存消耗可以通过空间复杂度来衡量。其中，原地排序算法，指的是空间复杂度 o(1)的算法。
3.排序算法的稳定性
稳定性指的是，如果待排序的序列中存在值相等的元素，经过排序以后，相等元素之间原有的先后顺序不变。
举个例子，如果现在我们要给电商交易系统的“订单”排序，订单有俩个属性，一个是下单时间，一个是订单金额。对于时间相同的订单，我们希望按照金额从小到大排序，对于金额相同的订单，我们希望按照下单时间从早到晚排序。那么我们可以按照俩个属性分别排一次续，如果是稳定的排序算法，假设第一次按时间排序，第二次按照金额排序，那么稳定算法可以保持金额相同的俩个对象，在排序后的前后顺序不变。
首先介绍一下三种排序算法：
冒泡排序
冒泡排序只会操作俩个相邻的数据，每次冒泡操作都会对相邻的俩个元素进行比较，如果不满足大小关系要求就让它俩互换。一次有效的冒泡至少会让一个元素移动到它应该在的位置，重复N次就完成了N个数据的排序工作。
实际上，冒泡还可以再优化。当某趟冒泡操作已经没有数据可以交换的时候，说明已经达到了完全有序，后面的冒泡就可以不需要了。因此，可以在循环中加一个flag，如果每趟有交换的话，就置为true，如果没有就置为false，跳出循环。
def bubble_sort(li:list)->list: if len(li) <=1: return li for i in range(len(li)): flag = False for j in range(0,len(li)-i-1): if li[j] >li[j+1]: li[j],li[j+1] = li[j+1],li[j] flag =True if not flag: return li return li
1.冒泡排序是一个原地排序算法，只涉及相邻数据的交换工作，只需要常量级的空间。
2.当相邻俩元素相等的时候，我们选择不交换，此时冒泡排序是稳定的排序算法。
3.最好的情况下，排序的数据有序，只要一次冒泡即可结束，最好的时间复杂度是o(n),最坏的情况是倒序排列，我们需要n次冒泡操作，最坏的情况时间复杂度是o(n**2)。
插入排序
插入排序的思想是，有一个有序的数组，当我们往里面添加一个新的数据后，用一种方法将继续保持数据有序： 遍历数组，找到数据数据应该插入的地方插入，把后面的数据都往后挪移位。
插入排序中包含俩种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个个数据插入到已排序区间时，需要与排序区间的元素依次比较大小，找到合适的插入位置。找到插入点以后，我们还需要将插入点之后的元素顺序往后移一位，这样才能腾出位置给插入元素。
def insert_sort(li:list)->list: if len(li) <=1: return li for i in range(1,len(li)): temp = li[i] j = i while j>=1: if li[j-1]>temp: li[j] = li[j-1] else: break j -=1 li[j] = temp return li
1.插入排序算法的空间复杂度是o(1)，是原地排序算法。
2.当对值相同的元素，我们可以选择将后面出现的元素插入到前面元素的后面，及相等的时候不比较，这样就可以保持原有的前后顺序不变，所以插入排序也是稳定的排序算法。
3.当原数据是有序的，我们如果从尾到头遍历一遍数据即可，此时最好时间复杂度为o(n)，如果数据是逆序的，每次插入都相当于在数组的第一个位置插入新的数据，最坏时间复杂度为o(n**2)。
插入排序的优化为希尔排序，由于插入排序在对几乎已经排好序的数据操作的时候效率非常高，可以达到线性排序效果，但是每次排序都只能移动一步，所以使用了递减步长的方法先把插入排序变得基本有序，然后当步长为1的时候即为插入排序。但是由于这样前期没有涉及相邻俩个元素的操作，所以希尔排序是一个不稳定的算法。
def shell_sort(li:list) ->list: if len(li) <=1: return li step = len(li)//2 while step >0: for i in range(step,len(li)): temp = li[i] j = i while j >= step: if li[j-step]>temp: li[j] = li[j-step] else: break j -=step li[j] = temp step = step //2 return li
为什么选择插入排序
在冒泡排序的时候我使用了Python的语法糖，而实际上冒泡排序的数据交换要比插入排序的移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个：
#冒泡排序
if li[j]>li[j+1]: temp = li[j] li[j] = li[j+1] li[j+1] = temp
#插入排序 if li[j]>li[j+1]: li[j+1] = li[j] else: break
对于一个逆序度为K的数组进行排序，用冒泡排序，总交换耗时是3*K个单位时间，而插入排序只要K个单位时间。
选择排序
选择排序的实现有点类似插入排序，也分已排序区间和未排序区间，但是不是移动以排好序的元素实现的交换，而是每一次从未排序的区间中找到最小的元素，将其放到已排区间的末尾。
def select_sort(li:list)->list: if len(li) <=1: return li for i in range(len(li)-1): min_index = i for j in range(i+1,len(li)): if li[j]<li[min_index]: min_index=j li[i],li[min_index] = li[min_index],li[i] return li
1.选择排序是一种原地排序算法，其空间复杂度为o(1)。
2.选择排序最好最坏和平均时间复杂度都为o(n**2),因为不管有序还是无序，都要二层循环遍历完。
3.选择排序不是一个稳定的排序算法，因为不涉及相邻元素的操作，以5,8,5,2,9数组为例，第一次找到了2，与第一个5交换顺序，那么俩个5的顺序就变了。
因此不仅执行语句多，时间复杂度没有优势，还不稳定，选择排序相比前俩个排序并没有多大优势。