题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
用归并排序算法,归并的时候,从后向前归并。
#include <iostream> using namespace std; int getreversenum(int *p1,int *p2,int left,int right) { if (!p1||!p2||left<0||right<0||left>right) { return -1; } if (left==right) { p2[left]=p1[left]; return 0; } int mid=left+(right-left)/2; int left_num=getreversenum(p1,p2,left,mid); int right_num=getreversenum(p1,p2,mid+1,right); int left_end=mid; int right_end=right; int merge_end=right; int count=0; while(left_end>=left&&right_end>=mid+1) { if (p1[left_end]>p1[right_end]) { p2[merge_end--]=p1[left_end--]; count+=right_end-mid; } else { p2[merge_end--]=p1[right_end--]; } } while(left_end>=left) { p2[merge_end--]=p1[left_end--]; } while(right_end>=mid+1) { p2[merge_end--]=p1[right_end--]; } for (int i=left;i<=right;++i) { p1[i]=p2[i]; } return left_num+right_num+count; } int _tmain(int argc, _TCHAR* argv[]) { int a[]={7,5,6,4}; int b[4]; int c=getreversenum(a,b,0,0); return 0; }