2.1，insertion，sort，《算法导论》答案

插入排序（Insertion Sort）是一种简单直观的排序算法，它通过构建有序序列，对于未排序数据进行逐个插入，从而得到排序结果。插入排序在实现上比较容易，且只需要一个额外的存储空间来保存当前待插入的元素，因此，它是实际应用中常用的排序算法之一。

算法原理

插入排序的核心思想就是：将待排序序列分成有序区和无序区，初始有序区只有一个元素。然后将无序区中的元素逐个插入到有序区中，从而扩大有序区，缩小无序区。具体实现过程如下：

1. 初始时，将第一个元素视为已排序序列（只有一个元素），第二个元素视为未排序序列（n-1个元素）。

2. 从未排序序列中取出第一个元素，依次和已排序序列中的元素进行比较，找到合适的位置插入该元素，使得插入后序列仍然有序。

3. 重复步骤2，直到未排序序列为空，此时排序完成。

举个例子，假设有一个待排序序列A={5,3,8,4,2}，那么它的排序过程如下：

初始状态： 5 | 3 8 4 2

第一轮插入：3 5 | 8 4 2

第二轮插入：3 5 8 | 4 2

第三轮插入：3 4 5 8 | 2

第四轮插入：2 3 4 5 8 |

在每次插入的过程中，我们都从被插入元素的右边开始，从后往前扫描已排序序列，找到第一个小于等于被插入元素的位置，然后将该元素插入到该位置后面。这个过程可以类比玩扑克牌时的插牌排序。

时间复杂度

在最坏情况下，即待排序序列为倒序排列时，每个元素都需要向前移动n-1个位置，因此时间复杂度是O(n^2)。但是，在实际应用中，如果序列本身已经基本有序，插入排序的效率会相对较高，实际运行效率往往比O(n^2)的复杂度要好。

空间复杂度

插入排序只需要一个额外的存储空间来保存当前待插入的元素，因此它的空间复杂度是O(1)。

稳定性

插入排序是一种稳定的排序算法，因为在插入新元素时，如果有相同的元素，它们就不会改变它们的相对位置。

优缺点

插入排序的优点是实现简单，适用于小规模数据的排序，且可以边排序边输出结果。它的缺点是在最坏情况下时间复杂度较高，且对于大规模数据排序效率较低。

总结

插入排序是一种基本的排序算法，在实际应用中有广泛的应用。它的时间复杂度在最坏情况下虽然较高，但是对于基本有序的序列排序效率很高，是比较实用的排序算法之一。