数组的逆序+归并+树状数组+快排

参考博文，代码原创

http://blog.csdn.net/alongela/article/details/8142965

http://blog.csdn.net/alongela/article/details/8119732

采用分治思想，将数组一分为2，先求字数组中的逆序，然后把子数组排好序，再合并有序数组求逆序，即在归并排序的过程中求逆序，算法时间复杂度可以由O(N^2)减为O(logN)

给定n个数，要求这些数构成的逆序对的个数。除了用归并排序来求逆序对个数，还可以使用树状数组来求解。

树状数组求解的思路：开一个能大小为这些数的最大值的树状数组，并全部置0。从头到尾读入这些数，每读入一个数就更新树状数组，查看它前面比它小的已出现过的有多少个数sum，然后用当前位置减去该sum，就可以得到当前数导致的逆序对数了。把所有的加起来就是总的逆序对数。

题目中的数都是独一无二的，这些数最大值不超过999999999，但n最大只是500000。如果采用上面的思想，必然会导致空间的巨大浪费，而且由于内存的限制，我们也不可能开辟这么大的数组。因此可以采用一种称为“离散化”的方式，把原始的数映射为1-n一共n个数，这样就只需要500000个int类型的空间。

离散化的方式：

struct Node

{

int val;

int pos;

};

Node node[500005];

int reflect[500005];

val存放原数组的元素，pos存放原始位置，即node[i].pos = i。

把这些结构体按照val的大小排序。

reflect数组存放离散化后的值，即reflect[node[i].pos] = i。

这样从头到尾读入reflect数组中的元素，即可以保持原来的大小关系，又可以节省大部分空间。

树状数组是一种非常巧妙的数据结构。对于一个普通数组，可以构造出一个对应的树状数组。普通数组中的元素存放的只是本身的信息，但树状数组中的元素存放的却是多个原数组的信息。

对于一个非负整数x，我们可以将它表示为二进制，设它的二进制形式中，结尾的0的个数为k。

对于树状数组，它的x位置上的元素表示的是原数组从x位置开始，往后数2^k个元素的信息（一般是它们的和，也可以是最大值或最小值）。

比如：

x=1时2^k=1，即它只包含本身的信息。其他奇数也一样。

x=2时2^k=2，即它包含2和1位置上的元素信息

x=4时2^k=4，即它包含4、3、2、1位置上的元素信息

x=6时2^k=2，即它包含6和5位置上的元素信息

……

对于x计算出它对应的2^k的方法非常简单，只要通过下面的函数：

int lowbit(int x)

{

return x & (-x);

}

这是一个非常巧妙的函数，对于树状数组的某个位置x而言，x + lowbit(x)表示它的上一级的结点，即包含它的信息的结点，而x - lowbit(x)表示比它小的不被它包含的最大结点。

比如当x=2时，lowbit(x)=2，则x+lowbit(x)=4，表示它的上一级结点是4，因为4包含了4、3、2、1的信息。

当x=7时，lowbit(x)=1，则x-lowbit(x)=6，表示比它小的不被它包含的最大结点是6。

树状数组的主要操作：

1、在某个位置的结点处增加一个值：在改变了原数组中元素的值之后，需要逐步向上修改上一级结点的信息。

2、统计第一个元素到当前元素的和：设置一个表示和的树状数组，然后使用上面的lowbit函数不断查找下一个不被包含的点，把所有的和加起来即可。

3、统计区间和：使用操作2中的方法，用较大的区间减去较小的区间就得到所求区间和了。

</pre><pre name="code" class="cpp">#include <iostream>

using namespace std;

#define N 500002

typedef struct mpair
{
	int data;
	int id;
}mpair;

//离散化输入数组到a当中，数据顺序和输入数据保持一致
//a中存储输入数据在输入数组中的排序序号
mpair inArray[N];
int a[N];
//树状数组，累计逆序，每一位只加1即可，统计和用于统计数字个数
int c[N];


void display(mpair *array, int len)
{
	int i;
	for (i = 0; i < len; ++i)
	{
		cout << array[i].data << " ";
	}
	cout << endl;
}

void displayIntArray(int *array, int len)
{
	int i;
	for (i = 0; i < len; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
}

//快速排序
void quickSort(mpair *array,  int st, int ed)
{
	if (st < ed) 
	{
		int left = st;
		int right = ed;
		mpair t = array[left];
		while (left < right)
		{
			while (left < right && array[right].data > t.data)
			{
				--right;
			}
			if (left < right)
			{
				array[left++] = array[right];
			}

			while (left < right && array[left].data < t.data)
			{
				++left;
			}
			if (left < right)
			{
				array[right--] = array[left];
			}
		}
		array[left] = t;

		quickSort(array, st, left - 1);
		quickSort(array, left + 1, ed);
	}
}

//返回2 ^ k, k为数据t末尾0的个数，用于计算树状数组中节点i的前驱和后继节点
int lowbit(int t)
{
	return t & (t ^ (t - 1));
	//return t & (-t);
}

//idx节点添加数据data
void addDataTreeArray(int *c, int n, int idx, int data)
{
	while (idx <= n)
	{
		c[idx] += data;
		idx += lowbit(idx);
	}
}

//0-idx区间的累加和
int getSumTreeArray(int *c, int n, int idx)
{
	int sum = 0;
	if (idx > n)
	{
		idx = n;
	}

	while (idx > 0)
	{
		sum += c[idx];
		idx -= lowbit(idx);
	}

	return sum;
}

void mergeReverse(int *c, int st, int ed, int *a, int &count)
{
	if (st < ed)
	{
		int mid = (st + ed) >> 1;
		mergeReverse(c, st, mid, a, count);
		mergeReverse(c, mid + 1, ed, a, count);

		int i,j,k;
		i = st;
		j = mid + 1;
		k = st;
		while (i <= mid && j <= ed)
		{
			if (c[i] < c[j])
			{
				a[k++] = c[i++];
			}
			else if (c[i] > c[j])
			{
				a[k++] = c[j++];
				++count;
			}
			else 
			{
				a[k++] = c[i++];
			}
		}

		if (i <= mid)
		{
			count += (mid - i) * (ed - mid);
		}

		while (i <= mid)
		{
			a[k++] = c[i++];
		}

		while (j <= ed)
		{
			a[k++] = c[j++];
		}

		//归并排序关键的一步必须把合并后的结果拷贝回原来的数组
		memcpy(c + st, a + st, (ed - st + 1) * sizeof(int));

		cout << "st = " << st << " ed = " << ed << endl;
	    displayIntArray(c, ed - st + 1);
		cout << endl;
	}
}

//归并排序算法求解
int mergeReverseNumber(int *c, int n)
{
	int *a = new int[n + 1];
	int count = 0;
	displayIntArray(c, n);
	mergeReverse(c, 0, n - 1, a, count);
	displayIntArray(c, n);
	cout << endl;
	delete []a;
	return count;
}

int main()
{
	int n;
	cin >> n;
	int i;
	//树状数组下标从1开始便于处理,0节点直接为0
	for (i = 1;  i <= n; ++i)
	{
		cin >> inArray[i].data;
		inArray[i].id = i;
	}

	display(inArray, n + 1);
	cout << endl;

	quickSort(inArray, 1, n);
	//离散化到数组a中，如果出现相同的数据则让离散化后的结果一致
	a[inArray[1].id] = 1;
	for (i = 2; i <= n; ++i)
	{
		if (inArray[i].data == inArray[i - 1].data)
		{
			a[inArray[i].id] = a[inArray[i - 1].id];
		}
		else
		{
		    a[inArray[i].id] = i;
		}
	}

	display(inArray, n + 1);
	cout << endl;

	displayIntArray(a, n + 1);
	cout << endl;

	int count = 0;
	memset(c, 0, sizeof(c));
	for (i = 1; i <= n; ++i)
	{
		//树状数组中a[i]节点数据累加1次，累加会向上一级节点延伸，相当于数据a[i]出现了一次
		addDataTreeArray(c, n, a[i], 1);
		//input i data, how many data low than i, and how many data large than i after i
		//输入了i个数据，包括i在内(相等的)前面出现的数据(节点)个数，差值为比i大的数据个数，也即逆序数
		count += i - getSumTreeArray(c, n, a[i]);
	}
	cout << "reverse number is : " << count << endl;


	cout << endl;
	cout << "merge sort reverse number is : " << mergeReverseNumber(&(a[1]), n) << endl;
	return 0;

}