白話経典アルゴリズムシリーズの9集計から数列への逆序数対(マイクロソフト筆記試験問題)

まず原題を見てみましょう
 
マイクロソフトの2010年の筆記試験問題
1つの配列では、対数の前後の位置が大きさの順序と逆である、すなわち、前の数が後の数より大きい場合、逆シーケンス数対と呼ばれる.1つの配列における逆シーケンスの総数をこの配列の逆シーケンス数と呼ぶ.{2,4,3,1}のように、2と1,4と3,4と1,3と1は逆シーケンスペアであるため、配列全体の逆シーケンスペア個数は4であり、現在は配列が与えられ、その配列の逆シーケンスペア個数の統計が要求される.
 
数列の逆序数を計算するのは個数に対して最も簡単で、最も前から後ろに順番に各数字とその後ろの数字が逆序数対を構成できるかどうかを統計します.コードは次のとおりです.

#include 
int main()
{
	printf("             
");    
	printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --

");    

	const int MAXN = 8;
	int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};
	
	int nCount = 0;
	int i, j;
	for (i = 0; i < MAXN; i++)
		for (j = i + 1; j < MAXN; j++)
			if (a[i] > a[j])
				nCount++;

	printf("     : %d
", nCount);
}

実行結果は次のとおりです.
この方法は二重ループを用い,時間的複雑さはO(N^2)であり,あまり優雅ではない方法である.そこで私たちは他の方法で解決しようとした.
 
「白話古典アルゴリズムシリーズの5つの集計ソートの実現」で集計ソートを観察する--集計数列(1,3,5)と(2,4)を観察するとき:
1.前の数の列の1を先に取り出します.
2.次の数の列の中の2を取り出して、明らかに!この2と前の3,5はいずれも逆序数対,すなわち3と2を構成することができ,5と2はいずれも逆序数対である.
3.前の列の3を取り出します.
4.次に、後の数の列の4を取り出し、同様に、この4と前の数の列の5とは逆シーケンスの対を構成することができることが分かる.
これで逆シーケンスペアの統計が完了し,集計ソートの時間的複雑度はO(N*LogN)であるため,集計ソートから数列の逆シーケンスペアへの解法の時間的複雑度は同様にO(N*LogN)であり,以下にコードを与える.

//             
#include 
int g_nCount;
void mergearray(int a[], int first, int mid, int last, int temp[])
{
	int i = first, j = mid + 1;
	int m = mid,   n = last;
	int k = 0;

	while (i <= m && j <= n) //a[i]       a[j]     
	{
		if (a[i] < a[j])
			temp[k++] = a[i++];
		else
		{
			temp[k++] = a[j++];
			//a[j]               
			g_nCount += m - i + 1;
		}
	}

	while (i <= m)
		temp[k++] = a[i++];

	while (j <= n)
		temp[k++] = a[j++];

	for (i = 0; i < k; i++)
		a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		mergesort(a, first, mid, temp);    //    
		mergesort(a, mid + 1, last, temp); //    
		mergearray(a, first, mid, last, temp); //          
	}
}

bool MergeSort(int a[], int n)
{
	int *p = new int[n];
	if (p == NULL)
		return false;
	mergesort(a, 0, n - 1, p);
	return true;
}

int main()
{
	printf("                   
");    
	printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --

");    

	const int MAXN = 8;
	int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};

	g_nCount = 0;
	MergeSort(a, MAXN);
	printf("     : %d
", g_nCount);
	return 0;
}

実行結果:
 
 
さて、ここまで紹介した後、どのように数列の逆序数を求めるかはすでによく認識されていると信じています.文章で使われている「知識の移行」という方法は悪くありません.
 
 
転載は出典、原文住所を明記してください.http://blog.csdn.net/morewindows/article/details/8029996