插入排序的平均时间复杂度为 O(n2)O(n2)。我们需要找出一个平均时间复杂度同样是 O(n2)O(n2) 的排序算法。

以下是各个选项的时间复杂度分析：

A. 堆排序（Heap Sort）

• 堆排序的平均时间复杂度为 O(nlog⁡n)O(nlogn)，因此它不是 O(n2)O(n2)。

B. 冒泡排序（Bubble Sort）

• 冒泡排序的平均时间复杂度为 O(n2)O(n2)，这与插入排序的时间复杂度相同。

C. 归并排序（Merge Sort）

• 归并排序的平均时间复杂度为 O(nlog⁡n)O(nlogn)，因此它也不是 O(n2)O(n2)。

D. 希尔排序（Shell Sort）

• 希尔排序的时间复杂度较为复杂，因为它依赖于增量序列的选择。希尔排序的平均时间复杂度通常认为是介于 O(n)O(n) 和 O(n2)O(n2) 之间，具体取决于增量序列的选择。

因此，平均时间复杂度与插入排序相同的是 B. 冒泡排序。冒泡排序的平均时间复杂度为 O(n2)O(n2)，这与插入排序的时间复杂度相匹配。

38:35