计算序列的逆序数实现

---

    本文介绍计算序列的逆序数算法的实现，对应于《算法导论》（第二版）P24，思考题2-4。

    作者：tyc611.cublog.cn，2008-03-02

---

问题描述

 

    设A[1..n]是一个包含n个不同数的数组。如果在iA[j]，则(i, j)就称为A中的一个逆序对（inversion）。给出一个算法，它能用Θ(nlgn)的最坏运行时间，确定n个元素的任何排列中逆序对的数目。

 

算法思想

 

    算法实现类似于合并排序，但需要额外处理逆序数的计数。因此，逆序数的计算相当于合并排序的副产品。

 

算法实现

 

    使用C++实现如下：

 

/**
 * InversionNum.cpp
 * @Author Tu Yongce
 * @Created 2008-2-20
 * @Modified 2008-2-20
 * @Version 0.1
 */

// 《算法导论》（第二版）P24，思考题2-4：逆序对

/**
 * 设A[1..n]是一个包含n个不同数的数组。如果在iA[j]，则(i, j)就称为A中的
 * 一个逆序对（inversion）。
 * d) 给出一个算法，它能用Θ(nlgn)的最坏运行时间，确定n个元素的任何排列中逆序对的数目。
 */

#include <cassert>
#include <algorithm>
#include <iostream>

using namespace std;

// 计算序列[begin, end)中的逆序数个数（序列不包括end所指元素）

template <typename T>
size_t calcInversionNum(T *begin, T *end)
{
    if (begin + 1 >= end)
        return 0;

    T *mid = begin + (end - begin) / 2;

    size_t num = calcInversionNum(begin, mid);
    num += calcInversionNum(mid, end);
    num += mergeSubSeq(begin, mid, end);

    return num;
}

// 合并两个非降序子序列，并返回逆序数

template <typename T>
size_t mergeSubSeq(T *begin, T *mid, T *end)
{
    size_t size = end - begin;
    T *tmp = new T[size];
    T *p = begin, *q = mid, *r = tmp;

    size_t num = 0;

    while (p < mid && q < end) {
        if (*p <= *q)
            *r++ = *p++;
        else {
            num += mid - p;
            *r++ = *q++;
        }
    }

    if (p == mid) {
        while (q < end)
            *r++ = *q++;
    } else {
        while (p < mid)
            *r++ = *p++;
    }

    copy(tmp, tmp + size, begin);
    delete [] tmp;

    return num;
}

template <typename T>
void printNum(T num)
{
    cout << num << " ";
}

void testInversionNum()
{
    int arr[5] = {2, 3, 8, 6, 1};
    assert(calcInversionNum(arr, arr + sizeof(arr) / sizeof(arr[0])) == 5);
    for_each(arr, arr + sizeof(arr) / sizeof(arr[0]), printNum<int>);
    cout << endl;

    double arr2[10] = {1, 4, 4.3, 9, 24, 4, 23, 9, 2, 9};
    assert(calcInversionNum(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0])) == 15);
    for_each(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]), printNum<double>);
    cout << endl;
}


运行结果如下：

1 2 3 6 8

1 2 4 4 4.3 9 9 9 23 24

请按任意键继续. . .

---