数组中逆序对

题目： 在数组中的两个数字，如果前面的一个数字大于后面的数字，则这两个数字为一个逆序对。输入一个数组，求这个数组的逆序对个数。例如：给定数组{5,8,3,1} ，则有<5,3>、<5,1>、<8,3>、<8,1>、<3,1> 这5个逆序对。

问题分析：我采用两种方法来解决这个问题：

        1）考虑到二叉搜索树中每个节点X，它的左子树所有关键字的值小于节点X的值，而右子树的所有关键字的值大于节点X的值，根据这种特点设计一种数据结构存储每一节点，数据结构如下所示：

                                   struct treeNode{

                                    int value;

                                    searchTree left;

                                    searchTree right;

                                    int rightChildNum;     //用于记录节点的右子树有多少个孩子

                                  };

程序读取数组的元素，构建节点并插入节点，在创建二叉搜索树过程中，改变结构体的rightChildNum成员的值来计算数组的逆序对。具体参考程序。

        2）运用归并排序方法解决这个问题，思路在《剑指offer》有详细说明。这里不再多说。

代码：1）的方法

#include <stdio.h>
#include <stdlib.h>

struct treeNode;
typedef struct treeNode *searchTree;
struct treeNode{
	int value;
	searchTree left;
	searchTree right;
	int rightChildNum;
};

static int inverseCount=0;   //用于统计逆序对的个数

searchTree
insert(int X, searchTree T){    //插入一个节点时改变结构体中rightChildNum成员值
	if(T==NULL){
		T = malloc(sizeof(struct treeNode));
		if(T == NULL){
			printf("Out of space!\n");
			exit(1);
		}else{
			T->value = X;
			T->rightChildNum = 1;
			T->left = T->right = NULL;
		}
	}else if(X < T->value){
		inverseCount += T->rightChildNum;  //节点T及左孩子的个数为插入X节点时的逆序对数
		T->left = insert(X,T->left);
	}else if(X > T->value){
		T->rightChildNum++;              //增加节点T的左孩子个数
		T->right = insert(X,T->right);
	}

	return T;
}

searchTree 
createArrayNode(int array[],int N){
	int i;
	searchTree T=NULL;
	for(i=0; i<N; i++){
		T=insert(array[i],T);	
	}

	return T;
}

void
printTree(searchTree T){
	if(T!=NULL){
		printTree(T->left);	
		printf("%d:%d\t",T->value,T->rightChildNum);
		printTree(T->right);	
	}
}

void 
removeTree(searchTree T){
	if(T != NULL){
		removeTree(T->left);	
		removeTree(T->right);
		if(T->left==NULL && T->right==NULL)
			free(T);
	}
}

int 
main(int argc,char **argv){
	searchTree T;
//	int array[6]={7,5,8,6,4,9};
//	int array[4]={7,5,6,4};
//	int array[7]={7,9,2,4,6,8,13};
    int array[]={7,5,8,6,4,9,14,21,1,52,49,2,56,27,128,65,47,23,57,98,10,17,72};
	T=createArrayNode(array,23);
	printTree(T);
	printf("\n");
	printf("Inverse Count is: %d\n",inverseCount);
	removeTree(T);
	return 0;
}
           

      2）归并排序的代码：

头文件："fatal.h"

#include <stdio.h>
#include <stdlib.h>

#define		Error(str)        FatalError(str)
#define		FatalError(str)	  fprintf(stderr,"%s\n",str),exit(1)
           

#include "fatal.h"

typedef int ElementType;

int
Merge( ElementType A[], ElementType tmpArray[], int lPos, int rPos, int rightEnd ){
	int leftEnd, numElements, tmPos;
	int i, count = 0;

	leftEnd = rPos-1;
	tmPos = rightEnd;
	numElements = rightEnd-lPos+1;

	while( lPos <= leftEnd && rPos <= rightEnd )
		if( A[leftEnd] > A[rightEnd] ){
			tmpArray[tmPos--] = A[leftEnd--];
			count += rightEnd - rPos + 1;
		}else
			tmpArray[tmPos--] = A[rightEnd--];

	while( lPos <= leftEnd )
			tmpArray[tmPos--] = A[leftEnd--];
	while( rPos <= rightEnd )
			tmpArray[tmPos--] = A[rightEnd--];

	for( i=0; i < numElements; i++, lPos++ )
		A[lPos] = tmpArray[lPos];

	return count;
}

int
MSort( ElementType A[], ElementType tmpArray[], int left, int right ){
	int Center;
	int count, leftCount, rightCount;

	if( left >= right )
		return 0;	
	
	Center = ( left + right ) / 2;
	leftCount = MSort( A, tmpArray, left, Center );
	rightCount = MSort( A, tmpArray, Center + 1, right );
	count = Merge( A, tmpArray, left, Center + 1, right );

	return count + leftCount + rightCount;
}

int
Mergesort( ElementType A[], int n ){
	ElementType *tmpArray;
	int count;

	tmpArray = malloc( n*sizeof(ElementType) );
	if( tmpArray != NULL ){
		count = MSort( A, tmpArray, 0, n-1 );
		free( tmpArray );
	}else
		FatalError( "No space for tmp array!!!" );

	return count;
}


int 
main(){
	int count;
//	ElementType arr[]={23,1,5,75,23,9,24,16,92,4};
	ElementType arr[]={7,5,6,4,2};

	count = Mergesort(arr,5);

	printf("inverse numbers is: %d\n",count);
	return 0;
}
           

参考文献：

《数据结构与算法分析-c语言描述》（美）Mark Allen Weiss

希望大家能够多多交流！