c++ - 确定插入排序中执行的移位数？

我正在尝试解决这个问题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;
 }

最佳答案

插入排序中进行交换的次数等于数组中inversions的数目(乱序的元素对的数目)。有一个well-known divide-and-conquer algorithm用于计算在时间O(n log n)中运行的数组中的反转次数。它基于mergesort的稍微修改后的版本，我认为编写它应该不会有太多麻烦。

关于c++ - 确定插入排序中执行的移位数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35208616/