问题思考
插入排序和冒泡排序的时间复杂度相同，都是O(n^2)，在实际软件开发里，为什么更倾向于使用插入排序算法而不是冒泡排序算法呢？
如何分析一个排序算法
排序算法的执行效率
1 . 最好情况、最坏情况、平均情况时间复杂度
分析排序算法的时间复杂度是，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，还要说出最好、最坏时间复杂度对应的要排序的原始数据长什么样。
2 . 时间复杂度的系数、常数、低阶
尽管表示时间复杂度时，忽略了系数、常数、低阶。但实际软件开发中，排序的数据可能是10个、100个、1000个这样的小规模数据，因而对于同一阶时间复杂度的排序算法，在比较时，应该把系数、常数和低阶考虑进来。
3 . 比较次数和交换（移动）次数
基于比较的排序算法在执行过程中，会涉及到两种操作，一种是比较元素大小，另一种是元素交换或移动。
排序算法的内存消耗
内存消耗可以通过空间复杂度来衡量。针对排序算法的空间复杂度，引入一个新概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。
插入排序、冒泡排序、选择排序都是原地排序算法。
排序算法的稳定性
稳定性指：如果待排序的序列中存在值相等的元素，经过排序后，相等元素之间原有的先后顺序不变。
相等元素之间原有的先后顺序没有变，这种排序算法叫作稳定的排序算法；否则，叫作不稳定的排序算法。
为什么要考察排序算法的稳定性？
场景举栗
比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。
如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？
思路分析
-
最先想到的方法是：先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。
-
更好的方法是：借助稳定排序算法。先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，再用稳定排序算法，按照订单金额重新排序。两遍排序之后，得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。
-
原因：稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，因为用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。
冒泡排序
排序过程
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
优化过程
当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，就不用再继续执行后续的冒泡操作。
代码
def bubble_sort(lt):
length = len(lt)
flag = False
for i in range(0,length):
for j in range(i+1,length):
if lt[i] > lt[j]:
lt[i], lt[j] = lt[j], lt[i] #数据交换
flag = True
if not flag:
break
return lt
分析
1 . 冒泡排序只涉及相邻数据的交换操作，只需常量级的临时空间，空间复杂度为O(1)，所以是一个原地排序算法。
2 . 冒泡排序中只有交换才改变两个元素的前后顺序。为了保证其稳定性，当相邻元素相等时，不做交换，那么相同大小的数据在排序前后不会改变顺序。所以冒泡排序是稳定的排序算法。
3 . 最好情况下，排序数据已经是有序的，只进行一次冒泡操作，所以时间复杂度是O(n)；最坏情况是，排序的数据刚好是倒序排列的，需要进行n次冒泡操作，所以时间复杂度为O(n^2)；
平均时间复杂度，采用一种不严格的方法，通过有序度和逆序度两个概念来分析。
有序度：数组中具有有序关系的元素对的个数。（默认，从小到大是有序的）
例：2,4,3,5这组数据的有序度为：5，分别是(2,4),(2,3),(2,5),(4,5),(3,5)；同理，对于一个倒序排列的数组，有序度为0；对于一个完全有序的数组，比如2,3,4,5，有序度就是n*(n-1)/2，也就是6。把这种完全有序的数组的有序度叫作满有序度。
逆有序度：其定义跟有序度正好相反。
逆有序度 = 满有序度 - 有序度
排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，说明排序完成。
冒泡排序中，包含两个操作，比较和交换。每交换一次，有序度就加1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是等于n*(n-1)/2 - 初始有序度。对于2,4,3,5这组数据来说，6-5=1，只需进行1次交换操作。
那么对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？
- 最坏情况：初始有序度为0，需要进行
n*(n-1)/2次交换 - 最好情况：初始有序度为
n*(n-1)/2，需要进行0次交换 - 平均情况：取一个中间值
n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。换句话说，平均情况下，需要n*(n-1)/4次交换操作，比较操作肯定比交换操作更多，而时间复杂度的上限是O(n^2)，所以平均情况下的时间复杂度就是O(n^2)。
插入排序
对于一个原本有序的数组，往里面加一个新数据后，如何继续保持数据的有序呢？很简单，只需要遍历数组，找到数据应该插入的位置将其插入即可。
插入排序就是借助这个思想来实现排序的。
排序过程
首先，将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
两种操作
一种是元素的比较，另一种是元素的移动。对于不同的查找插入点方法（从头到尾，从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，即为逆序度。（为什么移动次数=逆序度，可以拿个实例画一个图，很容易明白）
代码
def insertion_sort(lt):
length = len(lt)
for i in range(1, length):
value = lt[i]
for j in range(i-1,-1,-1):
if lt[j] > value:
lt[j+1] = lt[j] #数据移动
else:
break #位置确定
lt[j+1] = value #插入数据
return lt
分析
1 . 插入排序算法的运行并不需要额外的存储空间，空间复杂度为 O(1)，所以是一个原地排序算法。
2 . 插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素后面，保持原有前后顺序不变。所以插入排序是稳定的排序算法。
3 . 时间复杂度分析。
- 最好情况：数据已经有序，不需要搬移任何数据。如果从尾到头在有序数组里查找插入位置，每次只需比较一个数据就能确定插入位置。时间复杂度为
O(n)； - 最坏情况：数组是倒序的，每次插入都相当于在数组的第一个位置插入新数据，所有需要移动大量数据。时间复杂度为
O(n^2)； - 平均情况：在数组中插入一个数据的平均时间复杂度为
O(n)，对于插入排序来说，每次插入操作就相当于在数组中插入一个数据，循环执行n次插入操作。所以平均时间复杂度为O(n^2)。
选择排序
思路与插入排序类似，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间末尾。最开始没有已排好的区间，找到数组中最小元素，将其与第一个元素交换，然后再执行以上过程。
代码
def selection_sort(lt):
length = len(lt)
for i in range(0,length-1):
smallest_index = i
for j in range(i+1, length):
if lt[j] < lt[smallest_index]:
lt[j], lt[smallest_index] = lt[smallest_index], lt[j]
return lt
分析
1 . 选择排序空间复杂度为O(1)，是一种原地排序算法。
2 . 时间复杂度分析。最好情况、最坏情况和平均时间复杂度都为 O(n^2)。
3 . 选择排序是一种不稳定的排序算法。因为其每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样就破坏了稳定性。也因为此，相比于冒泡排序和插入排序，选择排序没那么好。
解答开篇
冒泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？
前面说过，冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。
但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动更复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。所以在对相同数组进行排序时，冒泡排序的运行时间理论上要长于插入排序。