闲来无事，复习复习经典的算法导论。看到了2-4，习题，计算逆序数的问题，忍不住实现了一下。
 
逆序数，是排列组合中常见的一个指标，可以用来衡量一个数列的杂乱成对（相对于顺序排列），在一些算法如水印算法中有广泛的应用。 如此如何快速的求得任意序列的逆
序数是关心的重点。常见的一种高效解法，是devid - and -conqure. 将序列平分成两段，分别计算逆序数，然后将两个有序的数列进行归并，并在归并过程中求取逆序数。两个
子序列的逆序数求取是较小规模的同样问题，可以用递归的方式完成。
 
简单说下如何在归并的过程中，计算逆序数。假设，有一个序列array[p, mid, r]. 其中array[p...mid], array[mid+1, ..., r]已经分别从小到大排好序。下面我们将两个子序列进行归
并。  假设当前的右边子序列（array[mid+1, ...., r]）的当前待比较元素下表为right, 左边的为left， 当array[left] <= array[right]， 这时候没有逆序发生（因为left的数 比right的
大）。当array[left] > array[right]， 是，right指向的元素具有逆序数，个数为他之前的所有的数，即mid-left+1。如此遍历下去，即可得到在归并中得到逆序数。
 
算法非常简单直白。 复杂度为： T(n) = 2T(n/2) + O(n).  根据master定理， T(n) = O(nlogn). 空间复杂度为2n，当然可以更小，2logn。
 
附上java实现的源代码。
 
public class MergInversionCount {
	public static int count(int[] array, int p, int r) {
		int inversionCount = 0;
		if (p < r) {
			int mid = (p + r) / 2;
			inversionCount += count(array, p, mid);
			inversionCount += count(array, mid+1, r);
			inversionCount += mergeInversion(array, p, mid, r);
		}
		return inversionCount;
	}

	private static int mergeInversion(int[] array, int p, int mid, int r) {
		int inversionCount = 0;
		int[] temp = new int[r-p+1];
		if(array.length < r)
			return inversionCount;
		int left = p;
		int right = mid + 1;
		int storeIndex = 0;
		while(left <= mid && right <= r)
		{
			if(array[left] > array[right])
			{
				inversionCount += mid-left+1; //当前right存在逆序数，数目等于mid-left+1
				temp[storeIndex] = array[right];
				right++;
			}
			else
			{
				temp[storeIndex] = array[left];
				left++;
			}
			storeIndex++;
		}
		if(left <= mid)
		{
			for(int i = left; i <= mid; i++)
			{
				temp[storeIndex] = array[i];
				storeIndex++;
			}
		}
		if(right <= r)
		{
			for(int i = right; i <= r; i++)
			{
				temp[storeIndex] = array[i];
				storeIndex++;
			}
		}
		
		for(int i = p; i <= r; i++)
		{
			array[i] = temp[i-p];
			
		}
		return inversionCount;
	}

}



import static org.junit.Assert.*;

import org.junit.Test;

public class MergInversionCountTest {

	@Test
	public void testCount() {
		int[] array = {1,5,6,7,4};
		int[] array2 = {1,5,6,7,4,3,11, 15, 13, 2, 8};
		
		int inversionCount = MergInversionCount.count(array, 0, 4);
		assertTrue(inversionCount == 3 );
		
		inversionCount = MergInversionCount.count(array2, 4, 10);
		assertTrue(inversionCount == 10 );

	}

}


 
 
 

/**
*求一组数的逆序数
*方案一（1）对数组中的每个数计算逆序数，之后再加和，得出整个数组的逆序数，复杂度O(n^2)
*方案二（2）借助归并排序的思想求解,复杂度O(nlogn)
*/

#include <stdio.h>
#include <malloc.h>

int compute1(int *begin, int *end)
{
    int *p, *q;
    int sum1, sum = 0;
    for(p = begin; p < end; p++)
    {
        sum1 = 0;
        for(q = p + 1; q <= end; q++)
        {
            if(*p > *q)
                sum1++;
        }
        sum += sum1;
        printf("%d\n",sum1);
    }

    return sum;
}

int compute2(int *begin, int *end)
{
    int sum = 0, i = 0;
    int *middle, *lbegin, *rbegin, *temp;
    int lsum, rsum;

    if(end - begin == 0)
        return 0;

    if(end - begin >= 1)
    {
        middle = begin + (end - begin) / 2;

        lsum = compute2(begin, middle);
        rsum = compute2(middle + 1, end);

        lbegin = begin;
        rbegin = middle + 1;
        temp = (int *)malloc(sizeof(int) * (end - begin + 1));
        while(lbegin <= middle && rbegin <= end)
        {
            if(*lbegin > *rbegin)
            {
                temp[i] = *rbegin;
                i++;
                rbegin++;
                sum += (middle - lbegin + 1);
            }
            else
            {
                temp[i] = *lbegin;
                i++;
                lbegin++;
            }
        }
        while(lbegin <= middle)
        {
            temp[i] = *lbegin;
            lbegin++;
            i++;
        }
        while(rbegin <= end)
        {
            temp[i] = *rbegin;
            rbegin++;
            i++;
        }

        i = 0;
        while(begin <= end)
        {
            *begin = temp[i];
            begin++;
            i++;
        }

        return sum + lsum + rsum;
    }

}

int main()
{
    int a[10] = {2,4,56,12,76,23,56,223,4,45};
    printf("数组a的逆序数为%d\n",compute1(a, a + 9));

    printf("数组a的逆序数为%d\n",compute2(a, a + 9));

    return 0;
}

  关于归并排序也可参考：http://blog.csdn.net/sjyu_ustc/article/details/10085343

在求解八数码问题时，因为要进行逆序数的计算判断两个结点的可达性，同奇偶的逆序数才能可达。如果只是八数，暴力解法还好，当数字多了之后如何知道逆序数呢。
题目描述
通过计算八数码节点的逆序数判断。如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如 2431 中，21，43，41，31 是逆序，逆序数是 4，为偶排列。

计算八数码节点的逆序数时将代表空格的 0 去除，如初始状态排列为 （1，3，2，4，5，6，7，8）  逆序数为：0+1+0+0+0+0+0+0=1 即为奇排列

目标状态排列为（1，2，3，8，4，7，6，5）  逆序数0+0+0+4+0+2+1+0=7 即为奇排列，具有同奇或同偶排列的八数码才能移动可达，否则不可达。
思路一
暴力穷举，每次扫描一个数时，遍历后方所有的数，那么这样的代价很大，O(n2)的时间复杂度。
思路二
分治的思想，自上而下划分，将大数组划分为小数组，只到划分到为数组中只有一个时，通过自下而上的排序的过程，计算出本数组中的数与相邻数组的逆序数，其实本质就是归并排序的过程。时间复杂度nlog2n。



那么怎么在归并排序的过程中进行分组呢?

例如下方，先考察相邻数组块的最大值，比较后若左侧大于右侧，则逆序数加上右侧剩余数目（因为两侧数据皆为有序），并加大数填入最终的位置，并将大数所在数组指针向右侧移动。直到指针全部移到最左端。当一侧的数据全部填入之后，将剩余部分填入最前端。


代码实现
作为数组，可以省略“分”的步骤，看成已经将每个数分成一个单位，直接进行“治”的过程。
`int sort(int *b, int start,int step,int num)//排序相邻的数据块
{
	int result = 0;
	if (start + step >= num)//如果是最后只剩一个数组块，不需要比较排序
	{
		return 0;
	}
	else//如果最后剩余两个数组块
	{
		int c[20];//临时保存最终排序完成的数组,从大到小排列，共rightend-leftend+1个元素
		int n = 0;
		int leftstart = start;
		int leftend = start + step - 1;//前一个数组的起始和最后
		int rightstart = start + step;
		int rightend;//后一个数组的起始和最后
		if (start + 2 * step > num)//最后一个数组块不足step个
		{
			rightend = num-1;
		}
		else//两个比较的数据块相同个数都为step个 
		{
			rightend = start + 2 * step - 1;
		}
		int left = leftend;
		int right = rightend;
		while (left>=leftstart&&right>=rightstart)
		{
			if (b[left] < b[right])
			{
				c[n++] = b[right];
				right--;
			}
			else
			{
				c[n++] = b[left];
				left--;
				result += right - rightstart + 1;
			}
		}
		int begin = start;
		if (left >= leftstart)//最小的一部分在左侧
		{
			begin = left + 1;
		}
		else//最小的一部分在右侧
		{
			for (int i = rightstart; i <= right; i++)
			{
				b[begin++] = b[i];
			}
		}
		for (int i = begin; i <= rightend; i++)
		{
			b[i] = c[--n];
		}
		return result;
	}

}
int inverse_number(int *a, int num)//归并排序
{
	int b[20];
	for (int i = 0; i < num; i++)
	{
		b[i] = a[i];
	}
	int sum = 0;
	int step = 1;
	while (step < num)
	{
		for (int i = 0; i < num; i =i + 2*step)
		{
			sum += sort(b, i, step,num);
		}
		step = step * 2;
	}
	return sum;
}`

优化
当经过一轮排序，所有数据未发生改变即可停止。

奇数码问题 Page38 归并排序计算逆序对
逆序对问题树状数组也可解决
如何转化为逆序对的奇偶性问题？？

证明：

空格的水平移动不会影响逆序对数

空格的上下移动会将一个数$x$与空格交换，即将$x$移动到$n-1$个元素之后或之前。

现在假设移动到$n-1$个元素之前

假设这$n-1$个元素中有$k$个比$x$小，那么移动之后逆序对数变化量为$|(n-1-k)-k|=|n-1-2k|$，$n-1$为偶数，$2k$也为偶数，故逆序对变化量也为偶数。
代码过于繁琐了，就当水篇博客

代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#include<map>
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x<b;x++)
#define W(x) printf("%d\n",x)
#define WW(x) printf("%lld\n",x)
#define pi 3.14159265358979323846
#define mem(a,x) memset(a,x,sizeof a)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=2e6+7;
const int INF=1e9;
const ll INFF=1e18;
int a[maxn],b[maxn],aa[maxn],n,m,x;
ll cnt1,cnt2;
void merge1(int l,int r)
{
    int mid=(l+r)>>1;
    int i=l,j=mid+1;
    rep(k,l,r)
    {
        if (j>r||i<=mid&&a[i]<=a[j])b[k]=a[i++];
        else b[k]=a[j++],cnt1+=mid-i+1;
    }
    rep(k,l,r)a[k]=b[k];
}
void merge2(int l,int r)
{
    int mid=(l+r)>>1;
    int i=l,j=mid+1;
    rep(k,l,r)
    {
        if (j>r||i<=mid&&aa[i]<=aa[j])b[k]=aa[i++];
        else b[k]=aa[j++],cnt2+=mid-i+1;
    }
    rep(k,l,r)aa[k]=b[k];
}
void merge_sort1(int l,int r)
{
    int mid=(l+r)>>1;
    if (l<r)
    {
        merge_sort1(l,mid);
        merge_sort1(mid+1,r);
        merge1(l,r);
    }
}
void merge_sort2(int l,int r)
{
    int mid=(l+r)>>1;
    if (l<r)
    {
        merge_sort2(l,mid);
        merge_sort2(mid+1,r);
        merge2(l,r);
    }
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        cnt1=0;cnt2=0;m=1;
        rep(i,1,n)
        {
            rep(j,1,n)
            {
                scanf("%d",&x);
                if (x!=0)a[m++]=x;
            }
        }
        m=1;
        rep(i,1,n)
        {
            rep(j,1,n)
            {
                scanf("%d",&x);
                if (x!=0)aa[m++]=x;
            }
        }
        merge_sort1(1,n*n-1);
        merge_sort2(1,n*n-1);
        if (cnt1%2==cnt2%2)printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}