插入排序就如同我们整理扑克牌一样，它把数据分为已排序和未排序两部分。一开始，已排序部分只有第一个元素，其余元素都在未排序部分。然后从未排序部分依次取出元素，将其插入到已排序部分的合适位置，在插入时，需要将比它大（或小，取决于升序还是降序）的元素依次向后移动，腾出插入的位置 。通过这样一次次的插入操作，未排序部分逐渐为空，已排序部分逐渐包含所有元素，最终完成整个数据的排序 。

1. 初始化：默认数组的第一个元素已经处于排序状态，所以我们从第二个元素开始处理。例如，对于数组[3, 1, 7, 5, 2]，我们先认为3是已排序部分，[1, 7, 5, 2]是未排序部分。

2. 迭代过程：取出未排序部分的第一个元素，在已排序部分从后向前扫描。比如现在未排序部分第一个元素是1，已排序部分是[3]，从后向前和3比较，因为1 < 3，所以要把3向后移动一位，然后把1插入到原来3的位置，这样已排序部分就变成了[1, 3]，未排序部分变为[7, 5, 2] 。接着，未排序部分第一个元素是7，已排序部分是[1, 3]，从后向前比较，7 > 3且7 > 1，所以7直接插入到已排序部分的末尾，已排序部分变为[1, 3, 7]，未排序部分变为[5, 2] 。以此类推，每次都从未排序部分取元素插入已排序部分。在比较过程中，如果已排序部分的元素大于当前要插入的元素，就将该元素向后移动一位，为插入元素腾出位置，直到找到合适的插入点。

3. 举例说明：下面我们用数组[3, 1, 7, 5, 2]来详细展示每一轮插入排序的操作过程。

• 第一轮：已排序部分为[3]，未排序部分为[1, 7, 5, 2]。取出未排序部分的第一个元素1，与已排序部分的3比较，1 < 3，将3向后移动一位，把1插入，得到已排序部分[1, 3]，未排序部分[7, 5, 2] 。用图表示如下：

• 初始数组：[3, 1, 7, 5, 2]

• 已排序：[3]，未排序：[1, 7, 5, 2]

• 比较1和3，移动3，插入1，新的已排序：[1, 3]，未排序：[7, 5, 2]

• 第二轮：已排序部分[1, 3]，未排序部分[7, 5, 2]。取出7，与已排序部分从后向前比较，7 > 3且7 > 1，直接将7插入已排序部分末尾，得到已排序部分[1, 3, 7]，未排序部分[5, 2] 。图示为：

• 已排序：[1, 3]，未排序：[7, 5, 2]

• 比较7和3、1，直接插入7，新的已排序：[1, 3, 7]，未排序：[5, 2]

• 第三轮：已排序部分[1, 3, 7]，未排序部分[5, 2]。取出5，与已排序部分从后向前比较，5 < 7，将7向后移动一位，继续比较5和3，5 > 3，将5插入3和7之间，得到已排序部分[1, 3, 5, 7]，未排序部分[2] 。图示如下：

• 已排序：[1, 3, 7]，未排序：[5, 2]

• 比较5和7，移动7，比较5和3，插入5，新的已排序：[1, 3, 5, 7]，未排序：[2]

• 第四轮：已排序部分[1, 3, 5, 7]，未排序部分[2]。取出2，与已排序部分从后向前比较，2 < 7，移动7，2 < 5，移动5，2 < 3，移动3，2 > 1，将2插入1和3之间，得到已排序部分[1, 2, 3, 5, 7]，未排序部分为空，排序完成。图示为：

• 已排序：[1, 3, 5, 7]，未排序：[2]

• 比较2和7、5、3，移动相应元素，插入2，新的已排序：[1, 2, 3, 5, 7]，未排序：[] 。

通过这样一步步的操作，数组就从无序状态逐渐变成了有序状态，这就是插入排序的完整过程。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
# 测试代码
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("排序后的数组:", sorted_arr)

• def insertion_sort(arr):：定义一个名为insertion_sort的函数，它接受一个列表arr作为参数，这个列表就是我们要排序的数组。

• for i in range(1, len(arr)):：外层循环从索引 1 开始遍历数组，因为我们默认第一个元素已经在已排序部分，所以从第二个元素（索引为 1）开始处理。

• key = arr[i]：将当前要处理的元素（即未排序部分的第一个元素）保存到key变量中，方便后续比较和插入操作。

• j = i - 1：定义一个变量j，它指向已排序部分的最后一个元素。

• while j >= 0 and key < arr[j]:：内层循环从已排序部分的最后一个元素开始向前遍历，只要j不小于 0（防止越界）并且当前要插入的元素key小于已排序部分中当前比较的元素arr[j]，就继续循环。

• arr[j + 1] = arr[j]：将已排序部分中大于key的元素向后移动一位，为key腾出插入位置。

• j -= 1：j向前移动一位，继续比较前一个元素。

• arr[j + 1] = key：当内层循环结束后，找到了key应该插入的位置，将key插入到该位置。

• 最后返回排序后的数组。

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        low, high = 0, i - 1
        while low <= high:
            mid = (low + high) // 2
            if key < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        j = i - 1
        while j >= low:
            arr[j + 1] = arr[j]
            j -= 1
        arr[low] = key
    return arr
# 测试代码
arr = [12, 11, 13, 5, 6]
sorted_arr = binary_insertion_sort(arr)
print("排序后的数组:", sorted_arr)

• low, high = 0, i - 1：初始化二分查找的范围，low指向已排序部分的起始位置，high指向已排序部分的末尾位置。

• while low <= high:：二分查找循环，只要查找范围不为空就继续。

• mid = (low + high) // 2：计算中间位置。

• 根据key和arr[mid]的大小关系，调整low或high，缩小查找范围。

虽然折半插入排序减少了比较次数，但是在最坏和平均情况下，它的时间复杂度仍然是 O (n²) 。这是因为插入排序的时间复杂度主要由比较次数和移动次数决定，折半插入排序只是减少了比较次数，而元素的移动次数并没有改变，在最坏情况下，仍然需要移动大量元素，所以整体时间复杂度没有降低 。不过在某些情况下，比如数据量较小或者数据基本有序时，折半插入排序的性能会优于传统插入排序 。

1. 最好情况：当输入数组已经是有序的时候，插入排序的性能表现最佳。每一次从未排序部分取出元素插入已排序部分时，只需要与已排序部分的最后一个元素比较一次，因为它是已排序部分最大（升序排序）的元素，且当前要插入的元素比它大（或相等），所以直接插入到已排序部分的末尾即可。对于长度为 n 的数组，总共需要进行 n - 1 次比较操作，因此最好情况下的时间复杂度为 O (n) 。比如数组[1, 2, 3, 4, 5]，从第二个元素2开始，它和1比较一次，然后插入；3和2比较一次插入，以此类推，总共比较次数就是 4 次（n - 1）。

2. 最坏情况：如果数组是逆序的，插入排序的时间复杂度会达到最坏。以插入第 i 个元素为例，它需要和已排序部分的前 i - 1 个元素依次比较，然后才能找到合适的插入位置。对于长度为 n 的数组，插入第 2 个元素时要比较 1 次，插入第 3 个元素时要比较 2 次，插入第 4 个元素时要比较 3 次…… 插入第 n 个元素时要比较 n - 1 次。那么总的比较次数就是 1 + 2 + 3 + … + n - 1 。根据等差数列求和公式\(S_n = \frac{n(n - 1)}{2}\)，当 n 趋于无穷大时，其时间复杂度为 O (n²) 。例如数组[5, 4, 3, 2, 1]，插入4时，和5比较 1 次；插入3时，和5、4比较 2 次；插入2时，和5、4、3比较 3 次；插入1时，和5、4、3、2比较 4 次，总比较次数为 1 + 2 + 3 + 4 = 10 次，符合公式计算结果。

3. 平均情况：在平均情况下，我们假设数组中元素的排列是随机的。对于每一个要插入的元素，平均需要和已排序部分的一半元素进行比较 。插入第 i 个元素时，平均比较次数约为\(\frac{i - 1}{2}\)。那么对于长度为 n 的数组，总的比较次数就是从 1 到 n - 1 的所有\(\frac{i - 1}{2}\)的累加 。即\(\sum_{i = 1}^{n - 1}\frac{i - 1}{2}\)，通过数学推导（这里简单说明，先将式子展开为\(\frac{0 + 1 + 2 +... + (n - 2)}{2}\)，再根据等差数列求和公式，分子部分和为\(\frac{(n - 2)(n - 1)}{2}\)，整体式子结果为\(\frac{(n - 2)(n - 1)}{4}\) ，当 n 趋于无穷大时，其时间复杂度仍为 O (n²) 。同样，元素的移动次数在平均情况下也与比较次数成正比，所以平均情况下插入排序的时间复杂度为 O (n²) 。

插入排序是一种稳定的排序算法。这意味着在排序过程中，相等元素的相对顺序不会发生改变 。在插入排序的过程中，当我们将一个元素插入到已排序部分时，如果遇到与它相等的元素，我们会将新元素插入到相等元素的后面，而不是前面 。比如有数组[2, 2', 1]（这里 2' 表示和 2 相等的另一个元素 ），在排序时，第一个2已经在已排序部分，当处理2'时，它会和第一个2比较，由于相等，2'会插入到第一个2的后面，最终排序结果为[1, 2, 2']，保持了相等元素2和2'原来的相对顺序 。

1. 小规模数据排序：插入排序的代码实现简单，并且在小规模数据情况下，其常数因子小，排序效率较高。例如，在一个小型的学生成绩管理系统中，若需要对某几个学生的成绩进行排序，使用插入排序可以快速完成任务 。假设只有 5 个学生的成绩需要排序，使用插入排序，其代码实现简单，不需要复杂的逻辑，能够迅速得到排序结果，而且由于数据量小，即使时间复杂度为 O (n²) ，其实际运行时间也很短，性能表现良好。

2. 部分有序数据排序：当数据已经部分有序时，插入排序的性能会显著提升。因为在这种情况下，大部分元素只需要移动较小的距离就能找到合适的位置，比较和移动的次数都会减少 。比如在一个电商平台的商品销量排行榜更新场景中，假设排行榜已经按照销量从高到低大致排好序，只有少数新上架的商品需要重新排序插入。这些新商品的销量与已排序部分的商品销量相比，只需要和已排序部分末尾的少数几个元素比较，就能确定插入位置，插入排序可以快速完成排序操作，提高排行榜更新的效率 。

插入排序最大的局限性在于面对大规模数据时，其时间复杂度较高。由于插入排序的平均和最坏时间复杂度都为 O (n²) ，当数据规模 n 非常大时，排序所需的时间会急剧增加，性能远远不如一些时间复杂度为 O (n log n) 的排序算法，如快速排序、归并排序等 。例如，要对一个包含 100 万个数据的数组进行排序，插入排序需要进行大量的比较和移动操作，其运行时间可能会非常长，而快速排序等算法则可以在相对较短的时间内完成排序任务，大大提高了处理效率 。

1. 时间复杂度：插入排序、冒泡排序和选择排序的平均时间复杂度和最坏时间复杂度都为 O (n²) 。但在最好情况下，插入排序和冒泡排序的时间复杂度为 O (n) ，而选择排序无论何种情况时间复杂度都是 O (n²) 。比如对于一个已经有序的数组，插入排序和冒泡排序只需要对数组进行一次遍历，而选择排序仍然需要进行大量的比较和交换操作 。在实际应用中，如果数据有一定的有序度，插入排序和冒泡排序会比选择排序更有优势。

2. 空间复杂度：三者的空间复杂度都为 O (1) ，都是原地排序算法，在排序过程中都只需要使用常数级别的额外空间 。

3. 稳定性：插入排序和冒泡排序是稳定的排序算法，而选择排序是不稳定的 。比如有数组[2, 2', 1]，在选择排序中，可能会将后面的1和第一个2交换，从而改变了2和2'的相对顺序 。而插入排序和冒泡排序会保持相等元素的相对顺序不变，在稳定性要求较高的场景下，如对学生成绩按照分数排序，相同分数的学生要保持原来的先后顺序，插入排序和冒泡排序更合适。

4. 适用场景：插入排序适用于小规模数据或部分有序的数据排序 。冒泡排序由于其交换操作较多，性能相对较差，在实际应用中使用较少，但在数据规模较小且对稳定性有要求时也可使用 。选择排序由于其时间复杂度不受数据初始状态影响，在一些对稳定性没有要求且数据规模较小的情况下可以使用，不过总体来说其应用场景也比较有限 。

1. 时间复杂度：快速排序的平均时间复杂度为 O (n log n) ，归并排序的时间复杂度始终为 O (n log n) ，而插入排序的平均和最坏时间复杂度为 O (n²) ，只有在最好情况下时间复杂度为 O (n) 。当数据规模较大时，快速排序和归并排序的性能远远优于插入排序 。例如对 100 万个随机数据进行排序，快速排序和归并排序能在较短时间内完成，而插入排序所需时间会非常长 。不过快速排序在最坏情况下（如数组已经有序或逆序时）时间复杂度会退化到 O (n²) ，而归并排序则相对稳定。

2. 空间复杂度：快速排序的空间复杂度在平均情况下为 O (log n) ，主要是递归调用栈的空间开销，在最坏情况下会达到 O (n) ；归并排序的空间复杂度为 O (n) ，因为在合并过程中需要额外的临时数组来存储数据 ；插入排序空间复杂度为 O (1) 。如果对空间复杂度要求较高，插入排序更具优势，而在空间允许的情况下，快速排序和归并排序更适合大规模数据排序 。

3. 稳定性：插入排序和归并排序是稳定的排序算法，快速排序是不稳定的 。在一些对稳定性有严格要求的场景中，如对商品按照价格排序，相同价格的商品要保持原有顺序，插入排序和归并排序可以满足需求，而快速排序则不适用 。

4. 适用场景：快速排序由于其平均性能优秀，在大多数情况下是处理大规模数据排序的首选算法 。归并排序则在外部排序（如对磁盘上的大文件排序）或者对链表进行排序时表现出色 。插入排序在小规模数据或者数据基本有序时表现较好 。