插入排序比较？

Question

如何计数插入排序中小于O(n^2)的比较数？

Answer 1

当我们插入一个元素时，我们交替比较和交换，直到(1)元素与其右边的元素进行不少于(2)我们到达数组的开头。在情况(1)中，有一个比较没有与交换配对。在情况(2)中，每个比较都与交换配对。对比较次数的向上调整可以通过计算从左到右的连续极小数(或您的插入排序工作)来计算，时间为O(n)。

num_comparisons = num_swaps
min_so_far = array[0]
for i in range(1, len(array)):
    if array[i] < min_so_far:
         min_so_far = array[i]
    else:
         num_comparisons += 1

Answer 2

正如所评论的，在小于O(n^2)的范围内这样做是很困难的，如果你必须为排序付出代价的话，也许是不可能的。如果您已经知道在每个外部迭代中所做的比较的数量，那么在O(n)中是可能的，但是排序的代价是在前一段时间支付的。

下面是计算方法内部比较的一种方法(在伪C++中)：

void insertion_sort(int p[], const size_t n, size_t & count)
{
  for (long i = 1, j; i < n; ++i)
    {
      auto tmp = p[i];
      for (j = i - 1; j >= 0 and p[j] > tmp; --j) // insert a gap where put tmp
        p[j + 1] = p[j];

      count += i - j; // i - j is the number of comparisons done in this iteration
      p[j + 1] = tmp;
    }
}

n是元素的数量，count是比较计数器，必须将变量设置为零。

Answer 3

如果我没记错的话，插入排序就是这样工作的：

A = unsorted input array
B := []; //sorted output array
while(A is not empty) {
    remove first element from A and add it to B, preserving B's sorting
}

如果插入到B是从左边通过线性搜索实现的，直到找到更大的元素为止，那么比较的数量就是(i,j)的对数，例如i < j和A[i] >= A[j] (我正在考虑稳定变量)。

换句话说，对于每个元素x，计算x之前具有较小或相同值的元素的数量。这可以通过从左侧扫描A来完成，将其元素添加到一些平衡的二进制搜索树中，该树还会记住每个节点下的元素数。在这样的树中，您可以在O(log n)中发现较小或等于某个值的元素数。总时间：O(n log n)。