特殊情况下插入排序的最坏情况比较
问题描述：
考虑一个插入在n个值上使用Sentinel排序，其中每个值在输入中只出现两次（所以n必须是偶数）。因此，比较的最佳情况输入是元素已经排序并且最佳情况下的确切比较次数是n-1。我相信比较的最坏情况输入是当元素被反向排序时。但在这种情况下，确切的比较次数是多少？为什么？特殊情况下插入排序的最坏情况比较
答
对具有1个元素的数组进行排序。在索引我插入到阵列
for(int i=1 ; i<n ; i++){
int valueForInsert = a[i];
.
.
.
}
为元件 和Ñ -1元素，我们在最坏的情况下我比较。 so 1 + 2 + 3 + ... +（n - 1）比较发生在反向排序阵列中。 和长度为n数组公式等于： （ñ *（ñ - 1））/ 2
你为什么不尝试一些小例子，并拿出一个合理的假设？ – 2015-02-11 15:05:18
我相信它是（n + 2）（n-1）/ 2。不知道是否正确。 – rightDrop 2015-02-11 15:14:08