数组中的逆序对 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 在数组中的两个数字假设前面一个数字大于后面的数字, 则这两个数字组成一个逆序对.

输入一个数组, 求出这个数组中的逆序对的总数.

使用归并排序的方法, 辅助空间一个排序的数组, 依次比較前面较大的数字, 算出总体的逆序对数, 不用逐个比較.

时间复杂度: O(nlogn)

代码:

/*

 * main.cpp

 *

 *  Created on: 2014.6.12

 *      Author: Spike

 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int InversePairsCore(int* data, int* copy, int start, int end) {

	if (start == end) {

		copy[start] = data[start];

		return 0;

	}

	int length = (end-start)/2;

	int left = InversePairsCore(copy, data, start, start+length);

	int right = InversePairsCore(copy, data, start+length+1, end);

	int i = start+length; //前半段最后一个数字的下标

	int j = end;

	int indexCopy = end;

	int count = 0;

	while (i>=start && j>=start+length+1) {

		if (data[i] > data[j]) {

			copy[indexCopy--] = data[i--];

			count += j-start-length;

		} else {

			copy[indexCopy--] = data[j--];

		}

	}

	for (; i>=start; --i)

		copy[indexCopy--] = data[i];

	for (; j>=start+length+1; --j)

		copy[indexCopy--] = data[j];

	return left+right+count;

}

int InversePairs (int* data, int length) {

	if (data == NULL || length < 0)

		return 0;

	int *copy = new int[length];

	for (int i=0; i<length; ++i)

		copy[i] = data[i];

	int count = InversePairsCore(data, copy, 0, length-1);

	delete[] copy;

	return count;

}

int main(void)

{

	int data[] = {7, 5, 6, 4};

	int result =  InversePairs (data, 4);

    printf("result = %d\n", result);

    return 0;

}

输出:

result = 5