1つの数列の逆シーケンスを出力
1,この問題アルゴリズムの導論は並べ替えの時に言及したことがある.
実装コードを見つけたが、構想ははっきりしている.
コア:2つの秩序シーケンスについて、逆シーケンスペアを探して、1回遍歴すればいいです.
2、実装コード:
実装コードを見つけたが、構想ははっきりしている.
コア:2つの秩序シーケンスについて、逆シーケンスペアを探して、1回遍歴すればいいです.
2、実装コード:
#include <iostream>
#include <cstring>
using namespace std ;
int inv(int data[], int n)
{
int left = (n >> 1);
int right = n - left;
int *tmp = new int[n];
int ret = (right > 1? (inv(data, left) + inv(data + left, right)) : 0);
int i = 0, j = 0;
while (i < left)
{
while ((j < right) && ((i == left || data[i] > data[left + j]))) // ,
//
{
tmp[i + j] = data[left + j]; // ,
j++; // ,
}
ret += j;
tmp[i + j] = data[i]; // ,
i++;
}
memcpy(data, tmp, sizeof(int) * n);
delete[] tmp;
return ret;
}
int main()
{
int data[] = {5, 4, 3, 2, 1};
cout << inv(data, sizeof(data)/sizeof(data[0])) << endl;
return 0;
}