归并排序及求逆序对

归并排序O(nlogn)及归并排序求逆序对数

归并排序及求逆序对

归并排序是一个以O(nlogn)时间复杂度进行排序的高级排序算法(相比较O(n^2)的低级排序来说)。以前只知道归并排序是一个可以并发的，可以用来进行外排序的算法，也知道它可以用来求逆序对。但是因为ACM中感觉平时使用快速排序就够了，求逆序对也可以使用权值线段树来做，所以对这个算法没有太在意。

今天看到了一道题，权值线段树开起来内存不够，也很代码量也有点大，于是今天学习了一下归并排序。看到代码发现非常好理解啊(当然我一次没写对233) 归并排序，简单的来说就是利用分治法，不断的把数组分到最小情况，然后再逐步向上合并。这里看起来有一点点像线段树的意思。 具体的看代码注释吧。

至于求逆序对，在归并排序的合并过程中，很容易发现每当我们将一个数字加入到临时数组中，都可以知道这个数字前面有多少个比它大的数字。这是因为我们合并的是两个相邻的数组，且这两个被合并的数组都是有序的。那么如果两个相邻的数组中，后面的数组的某个数字加入到了临时数组中，且前面的那个数组当前的数比被加入的这个数字大，那么可以知道前面的数组当前的数及其后面的所有数字都比被加入的这个数字大。

那么这时候我可以记录更新逆序对数。

code

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 10;
int a[maxn]; // 排序数组
int t[maxn]; // 排序过程中所需要临时数组

void merge( int l ,int m , int r )
{
    // i是左半部分指针，j是右半部分指针，k是临时数组指针
    // k可以是0的，这里是l只是方便后来的将t数组移动到a数组中不需要转换下标
    int i = l , j = m+1, k = l ;
    //进行合并操作，全部合并到临时数组t里面
    while( i <= m && j <= r )
    {
        if( a[i] > a[j] )
        {
            t[k++] = a[j++];
            // ans += m - i + 1 ;
            // 这里选择了后面的数组(即就是[m+1,r]部分，由j指向)
            // 那么可以知道[i,m]都是比a[j]大的。
            // 且[i,m]的下标都比j小
            // 所以a[i...m]和a[j]都是逆序对
        }
        else 
        {
            t[k++] = a[i++] ;
        }
    }
    //将剩下没有合并的数组直接扔到末尾
    while( i <= m ) 
        t[k++] = a[i++];
    while( j <= r )
        t[k++] = a[j++];
    // 放回原数组
    for( int i = l ; i <= r ; i++)
        a[i] = t[i];
}

void merge_sort( int l , int r )
{
    if( l < r )
    {
        int m = ( l + r ) / 2 ;
        // 先递归下去再进行合并
        merge_sort( l , m ) ;
        merge_sort( m + 1 , r );
        merge( l , m , r ) ;
    }
}


int main()
{
    for( int i = 1 ; i <= 10 ; i++)
        a[i] = i ;
    for( int i = 1 ; i <= 10 ; i++)
        cout << a[i] ;
    cout << endl ;

    merge_sort( 1 , 10 ) ;
    for( int i = 1 ; i <= 10 ; i++)
        cout << a[i] ;
    cout << endl ;
}

参考资料：

• 归并排序-求逆序数算法