插入排序比较分析

问：

我们都知道插入排序是如何工作的。我们获取每个元素并将其与左侧排列的排序部分进行比较。然后我们将该元素放在正确的位置，并将其他元素移动 1 个位置。

但是，究竟是什么决定了元素与其他元素进行比较的次数？这是它在原始排列中的位置和它在排序排列中的位置之间的距离吗？如果是这样的话，那是什么类型的关系呢？

从我在纸上写的案例来看，我认为距离（原始排列中的位置和排序排列中的位置之间）和比较次数之间应该存在线性关系。更重要的是，线性关系应该与因子 1 （再多 1 位 = 多 1 位比较）。

我很难在比较数量方面对插入排序进行 2 次优化。

1. 我们可以使用二进制搜索来确定每个元素在左侧排列的排序部分中的位置。由于 n-1、n-2、n-3 的移位，整体复杂性保持不变......悲观情景中每次迭代中的元素。但是，我们的比较较少（Olog（n））。
2. 我们可以从排列的两端开始，如果它们的顺序错误，我们可以交换 2 个元素。然后，在这种排列中，我们使用传统的插入排序。

现在让我担心的想法：第一个想法与我的理解相符，但我不确定我是否明白为什么第二个想法有意义。哪里有收益？如果距离和比较次数之间的关系与项 1 呈线性关系，那么我们为什么要以这种方式预处理我们的排列呢？我的意思是，每次我们“失去 1 个比较”并且不知道交换是否使我们更接近排序排列（或者我们？

如果我们选择“某种中位数”并通过将元素与该中位数进行比较进行预处理，我会理解，但这只会使中位数算法的中位数快速排序的递归步骤。除此之外，要找到中位数的中位数，比较的数量会更大。