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)，利用递归按照上

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

代码：

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 using namespace std;

 #define maxn 500010

 int a[maxn], b[maxn];

 long long count;

 void merge (int l, int r);

 int main ()

 {

     int n, i;

     while (scanf ("%d", &n), n)

     {

         memset (a, , sizeof (a));

         memset (b, , sizeof (b));

         for (i=; i<n; i++)

             scanf ("%d", &a[i]);

         count = ;//一定要用int64，int32会溢出

         merge (, n);

         printf ("%lld\n", count);

     }

     return ;

 }

 void merge (int l, int r)//归并排序，参数分别是子区间的位置

 {

     if (r - l <= )

         return ;

     int mid = l + (r - l) / ;

     merge (l, mid);

     merge (mid, r);

     int x = l, y = mid, i = l;

     while (x<mid || y<r)//对子序列进行排序，并且存到数组b里面

     {

         if (y >= r || (x < mid && a[x] <= a[y]))

             b[i ++] = a[x ++];

         else

         {

             if (x < mid)//记录交换次数

                 count += mid - x;

             b[i ++] = a[y ++];

         }

     }

     for (i=l; i<r; i++)//把排好序的子序列抄到a数组对应的位置

         a[i] = b[i];

 }

巴特西

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

最新文章

热门文章