为什么插入排序比冒泡排序更受欢迎？

【开篇问题的解答请放到最后再看噢~】
虽然冒泡排序和插入排序算法的时间复杂度都是O(n²)，冒泡排序涉及到元素的交换，插入排序涉及到元素的移动，交换次数和移动次数都是相同的，都是原始序列的逆序度。在冒泡排序中，元素的交换要三次赋值语句，而插入排序中元素的移动只需要一次赋值语句。所以若考虑到性能优化到极致，首选插入排序，在实际的试验中，对于相同的数据插入排序的执行时间也更快。除此之外，插入排序优化的空间也更大。

如何分析一个“排序算法”？

• 排序算法的执行效率

1. 最好情况、最坏情况、平均情况时间复杂度
   以及于此对应的要排序的原始数据是怎样的。
2. 时间复杂度的系数、常数、低阶
   因为当我们要排序的数据规模比较小时候，就要考虑这几点。而且对于同一阶时间复杂度的排序算法进行对比的时候，也要考虑这几点。
3. 比较次数和交换（或移动）次数
   对于基于比较的排序算法，一般就是要比较大小以及交换或者移动数据，所以在分析算法的执行效率的时候，也要把这两点考虑进去。

• 排序算法的内存消耗
  原地排序算法的概念，就是指空间复杂度为O(1)的排序算法。
• 排序算法的稳定性
  稳定性是指如果待排序的序列中，存在值相等的元素，经过排序后相等元素之间原有的先后顺序不变。
  为什么要考虑排序算法的稳定性呢？
  在实际的软件开发中，我们要排序的可能是一组对象，要依据对象的一个key进行排序，而对象的其他属性值可能也会对排序有要求。比如在电商交易系统中，对订单进行排序，要求按订单金额从小到大进行排序，同一金额的订单按时间顺序进行排序。按照我们的逻辑思维，我们会想着先按金额进行排序，然后对于金额相同的数据，按下单时间再进行排序。这样的思路是比较好想到的，但是实现起来就比较复杂。这时可以先按下单时间进行一次排序，再使用稳定性的排序算法按订单金额进行一次排序即可。

冒泡排序（Bubble Sort）

• 冒泡排序只会操作相邻的两个数据，每次冒泡操作就是将相邻的两个元素进行比较，看是否满足大小关系的需求，如果不满足就交换，经过一次冒泡，至少会让一个元素移动到它应该在的位置，这样重复n次，就可以把所有的数据都排好序。
• 冒泡排序的优化：当某次冒泡操作没有数据交换的时候，就说明已经完全有序了，就不需要再进行冒泡操作了。

分析

1. 冒泡排序算法是原地排序算法吗？
   是的，因为冒泡排序算法只涉及相邻元素的交换，只需要用到常数级别的临时空间，空间复杂度是O(1)，所以是原地排序算法。
2. 冒泡排序算法是稳定的排序算法吗？
   是的，我们在实现冒泡排序的时候，先比较再进行相邻元素的交换，对于相等的两个相邻元素，我们就可以不交换，这样原有的先后顺序就不会被破坏了。
3. 冒泡排序算法的时间复杂度是多少？
   最好的情况下，待排序的序列已经是有序的，那么进行一次冒泡就可以完成排序，因此最好情况时间复杂度是O(n)；最坏的情况就是，待排序的序列是完全倒序的，这就需要n次冒泡操作，因此最坏情况时间复杂度是O(n²)。
   一种“不严格”的分析平均时间复杂度的方法：
   有序度的概念——就是序列中有序的元素对的个数（默认从小到大为有序）。完全有序的序列，有序度为n*(n-1)/2，也被称作满有序度。倒序的序列，有序度就为0。冒泡排序中的交换操作，每交换一次，有序度就加一，所以排序中的交换操作次数是固定的，就是满有序度-初始有序度。最好情况下的交换次数是0，最坏情况下的交换次数是n*(n-1)/2，取个中间值代表平均情况，n*(n-1)/4。而复杂度的上限是O(n²)，所以平均情况的时间复杂度是O(n²)。

插入排序（Insertion Sort）

• 插入排序把数组中的数据分为两个区间，已排序区间和未排序区间，初始已排序区间只有一个元素，就是数组的第一个元素，每次从未排序区间中取一个元素，在已排序的区间中找到这个元素的位置，然后插入元素，重复这个操作，直到未排序区间没有元素。
• 插入排序包含元素的比较以及元素的移动。对于不同的查找插入点的方法，元素的比较次数是不同的，但是元素的移动次数是固定的，就是原始序列的逆序度。因为每移动一次，有序度就加一，最终完全有序。所以移动的次数就是原始序列的逆序度。

分析

1. 插入排序算法是原地排序算法吗？
   是的，因为每次移动的时候，只需要常数级别的临时空间来保存待插入的元素的值，所以空间复杂度就是O(1)。
2. 插入排序算法是稳定的排序算法吗？
   是的，在插入排序的时候，我们从左到右遍历数据，在进行比较确定插入位置的时候，对于相等的数据我们可以选择插在其后面。
3. 插入排序的时间复杂度是多少？
   如果要排序的数据已经是有序的，而且我们从尾到头在有序区间中查找插入位置，那么每次只需要比较一次即可，而且不需要进行移动操作，所以最好情况下时间复杂度是O(n)。如果数据都是倒序的，每次插入数据都要移动大量的数据，对应的就是最坏情况的时间复杂度为O(n²)。平均时间复杂度？？

选择排序（Selection Sort）

• 选择排序也分已排序区间和未排序区间，每次从未排序区间中查找到最小值的元素，放到已排序区间的尾部，最终得到排好序的序列。

分析

1. 选择排序算法的空间复杂度？
   空间复杂度是O(1)，是原地排序算法。
2. 选择排序算法的时间复杂度？
   最好情况、最坏情况、平均情况的时间复杂度都是O(n²)。因为在最好情况下，也就是序列已经有序的时候，也要进行n次从未排序的区间中选最小元素的操作，所以时间复杂度都是O(n²)。
3. 选择排序算法是稳定的排序算法吗？
   不是稳定的排序算法，因为选择到未排序区间的最小元素后，将最小元素和未排序区间的第一个元素（也就是插入到已排序区间的尾部）进行交换，这就可能破坏了相等的元素原本的先后顺序。