确定插入排序中执行的移位次数？

Question

我正在尝试解决这个问题http://www.mycodeschool.com/work-outs/sorting/7 问题是在插入排序中找不到任何变化。

我已经编写了代码，但无法弄清楚我在逻辑上哪里出错了

http://ideone.com/GGjZjw

#include<iostream>
#include<cstdio>
#include<cmath>
// Include headers as needed

using namespace std;

int main()
{
// Write your code here
int T,count,n,*a;
// int imin;
cin >> T;
int value,hole;

while(T--)
{
    cin >> n;
    count=0;
    a=new int[n];
    //reading the input array
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }

    // considering the 0th element to be already sorted and
    // remaining list unsorted
    for(int i=1;i<n;i++)
    {
        value=a[i];
        hole=i;
        // shifting 
        while(hole>0&&a[hole-1]>value)
        {
            // 
            a[hole]=a[hole-1];
            hole=hole-1;
            count++;
        }
        a[hole]=value;
    }
    // cout << count<<endl;
}
// Return 0 to indicate normal termination
return 0;
 }

Answer 1

插入排序中进行的交换次数等于数组中的反转次数（无序元素对的数量）。有一个众所周知的分治算法，用于计算在 O(n log n) 时间内运行的数组中的反转次数。它基于合并排序的一个稍微修改过的版本，我认为编码它应该不会有太多麻烦。