http://blog.csdn.net/seuliujiaguo/article/details/39555481 这是快排其他的应用
http://blog.csdn.net/seuliujiaguo/article/details/39404161 这是我前一个博文快排方法
题目:给定一个数组,比如5, 1, 2, 3, 4,求解该数组中逆序对的数目(这个数组包含4个逆序对,为5,1 5,2 5,3 5,4)
分析:可以采用类似归并排序方式,分而治之,将数组平分为两部分,计算前后两部分中存在的逆序对,在合并过程中,计算两部分之间存在的逆序对数目
#include "stdafx.h" #include <iostream> #include <string> using namespace std; //利用归并排序的方法统计逆序对 //将有二个有序数列a[first...mid]和a[mid...last]合并。 int mergearray(int a[], int first, int mid, int last, int temp[]) { int count=0;//统计逆序数 int i=first; //前一组的开始 int n=mid; //前一组的结束 int j=mid+1; //后一组的开始 int m=last; //后一组的结束 int k=last; //临时数组从后面开始放入数据 while (i<=n&&j<=m) { //从最后面比较二个数列,大的先放入临时数组中。 if (a[n]<a[m]) { temp[k--]=a[m--]; } else { temp[k--]=a[n--]; count=count+m-j+1;//如果前面数组的数大于后一个数组的数的话,那么后一个数组前面的数都是前面一个数组的数的逆序数。 } } //有数列为空,那直接将另一个数列的数据从末尾依次取出即可 while (i<=n) { temp[k--]=a[n--]; } while (j<=m) { temp[k--]=a[m--]; } for (i=first;i<=last;i++) { a[i]=temp[i]; } return count; } int mergesort(int a[], int first, int last, int temp[]) { if (first == last) { return 0; } else { int mid = (first + last) / 2; int left= mergesort(a, first, mid, temp); //左边的逆序数目 int right=mergesort(a, mid + 1, last, temp); //右边的逆序数目 int all=mergearray(a, first, mid, last, temp); //两者之间的逆序数目 return (left+right+all); } } int main() { int a[]={4,5,6,7}; int temp[4]; int res=mergesort(a,0,3,temp); return 0; }