數組中的逆序對 代碼(C)
題目: 在數組中的兩個數字如果前面一個數字大於後面的數字, 則這兩個數字組成一個逆序對.
輸入一個數組, 求出這個數組中的逆序對的總數.
使用歸並排序的方法, 輔助空間一個排序的數組, 依次比較前面較大的數字, 算出整體的逆序對數, 不用逐個比較.
時間復雜度: O(nlogn)
代碼:
/*
* main.cpp
*
* Created on: 2014.6.12
* Author: Spike
*/
/*eclipse cdt, gcc 4.8.1*/
#include
#include
#include
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
輸出:
result = 5
