hanyeah

假设A[1...n]是一个有n个不同元素的数组，若i<j且A[i]>A[j]，则对偶（i，j）称为A的一个逆序对。

求出数组[2, 3, 8, 6, 1]的5个逆序对。

按照定义实现的算法,时间复杂度O(n^2)：

代码如下：

var a = [2, 3, 8, 6, 1];
var p = reversePairs(a);
console.log('数组：', a.join(','));
console.log('逆序对个数：', p.length);
console.log('逆序对：', p);

function reversePairs(a){
	var r = [];
	var len = a.length;
	for(var i = 0; i < len - 1; i++){
		for(var j = i + 1; j < len; j++){
			if(a[i] > a[j]){
				//r.push([i, j]);
				r.push([a[i],a[j]]);
			}
		}
	}
	return r;
}

使用归并排序，可以使时间复杂度降为O(nlgn)：

代码如下：

var a = [2, 3, 8, 6, 1];
var p = [];
mergeReversePairs(a, 0, a.length, p);
console.log('数组：', a.join(','));
console.log('逆序对个数：', p.length);
console.log('逆序对：', p);

function mergeReversePairs(a, p, r, ){
	if(p < r - 1){
		var q = Math.floor((p + r) / 2);
		mergeReversePairs(a, p, q, );
		mergeReversePairs(a, q, r, );
		merge(a, p, q, r, );
	}
	return b;
}

function merge(a, p, q, r, ){
	var n1 = q - p;
	var n2 = r - q;
	var L = [];
	var R = [];
	for(var i = 0; i < n1; i++){
		L[i] = a[p + i];
	}
	for(var j = 0; j < n2; j++){
		R[j] = a[q + j];
	}
	L[n1] = Infinity;
	R[n2] = Infinity;
	var i = 0;
	var j = 0;
	for(var k = p; k < r; k++){
		if(L[i] < R[j]){
			a[k] = L[i];
			i++;
		}
		else {
			a[k] = R[j];
			
			j++;
		}
	}
}

其实就是用归并排序算法给数组排了序，排序过程中记录了一下逆序对，注意粗体部分。