1和0交错数组的插入排序分析

Question

对插入排序 N/2 1 与 N/2 0 交错排列的数组进行比较的次数是多少（例如，1 0 1 0 1 0 1 0 1 0）？ 关键在于计算反转的次数。但我不认为我算对了。

Answer 1

前面有 i 个零的零后面有 n/2 - i 个。答案是

n/2-1             n/2
 sum  (n/2 - i) = sum j = (n/2 + 1) (n/2) / 2.
 i=0              j=1

Answer 2

您将有 n*(n+2)/8 步。

当您在 i 位置插入任何 0 时，您必须向右移动 i/2 1s。任何 1 应该已经在正确的位置，因此不需要任何移动。