最新消息:点击查看大S的省钱秘笈

POJ 2299 Ultra-QuickSort C语言版

POJ题解 Slyar 3207浏览 4评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

利用归并求逆序对

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,

Ultra-QuickSort produces the output
0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 — the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

Slyar:题目本质就是求逆序对了,简单介绍一下。逆序对是指在序列{a0,a1,a2…an}中,若ai<aj(i>j),则(ai,aj)上一对逆序对。而逆序数顾名思义就是序列中逆序对的个数。例如: 1 2 3是顺序,则逆序数是0;1 3 2中(2,3)满足逆序对的条件,所以逆序数只有1; 3 2 1中(1,2)(1,3)(2,3)满足逆序对,所以逆序是3。由定义不能想象,序列n的逆序数范围在[0,n*(n-1)/2],其中顺序时逆序数为 0,完全逆序时逆序数是n*(n-1)/2。

可以利用归并排序时计算逆序个数,时间复杂度是nlog2n,而空间复杂度2n。 利用归并求逆序是指在对子序列s1和s2在归并时,若s1[i]>s2[j](逆序状况),则逆序数加上s1.length-i,因为s1中i后面的数字对于s2[j]都是逆序的。具体看注释吧。

PS.归并算法基本思路

设两个有序的子文件放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1中,待合并完成后将R1复制回R[low..high]中。

合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字,取关键字较小的记录复制到R1[p]中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。

重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。

#include 
#include 

#define MAX 500001

int n, a[MAX], t[MAX];
__int64 sum;

/* 归并 */
void Merge(int l, int m, int r)
{
    /* p指向输出区间 */
    int p = 0;
    /* i、j指向2个输入区间 */
    int i = l, j = m + 1;
    /* 2个输入区间都不为空时 */
    while(i <= m && j <= r)
    {
        /* 取关键字小的记录转移至输出区间 */
        if (a[i] > a[j])
        {
            t[p++] = a[j++];
            /* a[i]后面的数字对于a[j]都是逆序的 */
            sum += m - i + 1;
        }
        else
        {
            t[p++] = a[i++];
        }
    }
    /* 将非空的输入区间转移至输出区间 */
    while(i <= m) t[p++] = a[i++];
    while(j <= r) t[p++] = a[j++];
    /* 归并完成后将结果复制到原输入数组 */
    for (i = 0; i < p; i++)
    {
        a[l + i] = t[i];
    }
}

/* 归并排序 */
void MergeSort(int l, int r)
{
    int m;
    if (l < r)
    {
        /* 将长度为n的输入序列分成两个长度为n/2的子序列 */
        m = (l + r) / 2;
        /* 对两个子序列分别进行归并排序 */
        MergeSort(l, m);
        MergeSort(m + 1, r);
        /* 将2个排好的子序列合并成最终有序序列 */
        Merge(l, m, r);
    }
}

int main()
{
    int i;
    while(1)
    {
        scanf("%d", &n);
        if (n == 0) break;
        sum=0;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        MergeSort(0, n - 1);
        printf("%I64d\n", sum);
    }
    //system("pause");
    return 0;
}

转载请注明:Slyar Home » POJ 2299 Ultra-QuickSort C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (4)

  1. 确实不错啊,瞻仰
    涛声依旧7年前 (2013-08-05)回复
  2. merge sort 写的很清晰,逆序对分析也很到位! 学习了!Thanks!
    hua9年前 (2011-06-21)回复
  3. 把你的POJ上的每一篇报告仔细研读了一下,收获很多,真是非常感谢你~~~呵呵
    流觞10年前 (2011-04-18)回复
  4. 真是太好了,谢谢!
    Frank11年前 (2009-10-18)回复