逆序对(树状数组)

inversion.c

/**
 * @author monkindey
 * @date 2014.11.27
 * @description 用树状数组实现逆序对
 * @idea {
 *       数组离散化
 *       离散化数组进行树状数组操作
 * }
 */
#include <stdio.h>
#define MAX_SIZE 10
typedef struct Node Node;
struct Node{
	int data;
	int index;
};

int tree[MAX_SIZE] = {0};

int main() {
	void bubbleSort(Node *arr, int len);
	void update(int idx, int value);
	int getSum(int idx);

	// 9, 1, 0, 5, 4
	Node node[MAX_SIZE];
	int discreted[MAX_SIZE];
	// int discreted[MAX_SIZE] = {5, 2, 1, 4, 3};
	int n, i, j, result = 0;
	printf("%s\n", "please enter the length");
	scanf("%d", &n);
	printf("%s\n", "please enter your data");
	for(i = 0; i < n; i++) {
		scanf("%d", &node[i].data);
		node[i].index = i;
	}

	bubbleSort(node, n);

	// 离散化数组
	for(i = 1; i <= n; i++) {
		discreted[node[i - 1].index] = i;
	}

	for(i = 0; i < n; i++) {
		printf("%d\n",discreted[i]);
	}

	for(i = 1 ; i < n; i++) {
		update(discreted[i], 1);
		result += (i + 1) - getSum(discreted[i]);
		printf("result ---- %d\n", result);
	}

	for(j = 1; j < n + 1; j++) {
		printf("tree --- %d\n", tree[j]);
	}

	printf("%s\n", "=================================");

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

	return 0;
}

void update(int idx, int value) {
	int getLowBit(int num);
	int i;
	while(idx < 5) {
		tree[idx]++;
		idx += getLowBit(idx);
	}
}

// 求前缀和
int getSum(int idx) {
	int getLowBit(int num);
	int prefixSum = 0, i;
	while(idx > 0)  {
		prefixSum += tree[idx];
		idx -= getLowBit(idx);
	}
	return prefixSum;
}

int getLowBit(int num) {
	return num & (-num);
}

// 简单的冒泡排序
void bubbleSort(Node *arr, int len) {
	void swap(Node *arr, int i, int j);
	int i, j;
	for(i = 1; i < len; i++) {
		for(j = len - 1; j >= i; j--) {
			if(arr[j].data < arr[j - 1].data) {
				swap(arr, j, j - 1);
			}
		}
	}
}

void swap(Node *arr, int i, int j) {
	Node temp;
	temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}