求逆序对数总结 & 归并排序

69 阅读 0 评论 46 点赞

我是靠谱客的博主野性抽屉，最近开发中收集的这篇文章主要介绍求逆序对数总结 & 归并排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

用归并排序方式

最原始的方法的复杂度是O(n^2)。

使用归并排序的方式，可以把复杂度降低到O(nlgn).

设A[1..n]是一个包含N个非负整数的数组。如果在i〈 j的情况下，有A〉A[j]，则(i,j)就称为A中的一个逆序对。
例如，数组（3，1，4，5，2）的“逆序对”有<3,1>,<3,2><4,2><5,2>，共4个。

注：我觉得方法是在归并过程中，记录每次归并，后面的分组中被放到了前面的元素的个数。

的确是这样的。下面这个也是MergeSort的基本算法框架：

　int gCount = 0;

  template<class Iterator>int merge(Iterator begin, Iterator mid, Iterator end)

  {
   Iterator iL = begin;
   Iterator iR = mid;

   int count = distance(begin, end);
   vector<int> v(count);
   vector<int>::iterator it = v.begin();

   while(iL != mid && iR != end)
   {
       if(*iL <= * iR)
       {
           *it++ = *iL++;
       }
       else
       {
           gCount += distance(iL, mid);
           *it++ = *iR++;
       }
   }

   if(iL == mid) copy(iR, end, it);
   if(iR == end) copy(iL, mid, it);

   copy(v.begin(), v.end(), begin);

   return 0;

}

template<class Iterator>int mergeSort(Iterator begin, Iterator end)

{
   int count, step;
   count = distance(begin, end);

   if(count <= 1)
   {
       return 0;
   }

   step = count / 2;

   mergeSort(begin, begin + step);
   mergeSort(begin + step, end);

   merge(begin, begin + step, end);

   return 0;

}