首页 > 代码库 > poj 2299 Ultra-QuickSort 归并排序求逆序数对

poj 2299 Ultra-QuickSort 归并排序求逆序数对

题目链接:

  http://poj.org/problem?id=2299

题目描述:

  给一个有n(n<=500000)个数的杂乱序列,问:如果用冒泡排序,把这n个数排成升序,需要交换几次?

解题思路:

  根据冒泡排序的特点,我们可知,本题只需要统计每一个数的逆序数(如果有i<j,存在a[i] > a[j],则称a[i]与

a[j]为逆序数对),输出所有的数的逆序数的和用普通排序一定会超时,但是比较快的排序,像快排又无法统计

交换次数,这里就很好地体现了归并排序的优点。典型的利用归并排序求逆序数。

  归并排序:比如现在有一个序列[l,r),我们可以把这个序列分成两个序列[l,mid),[mid,r),利用递归按照上

述方法逐步缩小序列,先使子序列有序,再使子序列区间有序,然后再把有序区间合并,很好滴体现了分治的思想。

代码:

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 using namespace std; 6 #define maxn 500010 7  8 int a[maxn], b[maxn]; 9 long long count;10 11 void merge (int l, int r);12 int main ()13 {14     int n, i;15     while (scanf ("%d", &n), n)16     {17         memset (a, 0, sizeof (a));18         memset (b, 0, sizeof (b));19         for (i=0; i<n; i++)20             scanf ("%d", &a[i]);21         count = 0;//一定要用int64,int32会溢出22         merge (0, n);23         printf ("%lld\n", count);24     }25     return 0;26 }27 28 void merge (int l, int r)//归并排序,参数分别是子区间的位置29 {30     if (r - l <= 1)31         return ;32     int mid = l + (r - l) / 2;33     merge (l, mid);34     merge (mid, r);35     int x = l, y = mid, i = l;36     while (x<mid || y<r)//对子序列进行排序,并且存到数组b里面37     {38         if (y >= r || (x < mid && a[x] <= a[y]))39             b[i ++] = a[x ++];40         else41         {42             if (x < mid)//记录交换次数43                 count += mid - x;44             b[i ++] = a[y ++];45         }46     }47     for (i=l; i<r; i++)//把排好序的子序列抄到a数组对应的位置48         a[i] = b[i];49 }

 

poj 2299 Ultra-QuickSort 归并排序求逆序数对