POJ 1804 逆序数 解题（归并排序）

文章目录

• • 解法1：直接双重循环求解，n*n复杂度
  • 解法2：采用归并排序求解，复杂度nlgn

题目链接 http://poj.org/problem?id=1804 题目大意： 让一串无序数，在只能相邻数字交换的前提下，最短的次数变成有序，求该最短次数。 该最短次数=该序列的逆序数

解法1：直接双重循环求解，n*n复杂度

代码语言：javascript复制

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    const int N = 1001;
    int cyctime,len,len1,sum=0;
    int arr[N];
    int i=0,j=0,k=0,temp;
    memset(arr,0,sizeof(int)*N);
    cin >> cyctime;
    for(i = 0; i < cyctime;   i)
    {
        //cin.clear();
        cin >> len;
        len1=len;
        j=0;
        while(len1--)	//先输入数组
        {
            cin >> temp;
            arr[j  ] = temp;
        }
        for(j = 0; j < len;   j)	//从前往后依次比较
        {
            for(k = j 1; k < len;   k)
            {
                if(arr[j]>arr[k])
                {
                    sum  ;
                }
            }
        }
        cout << "Scenario #" << i 1 << ":" << endl;
        cout << sum << endl << endl;
        sum = 0;
    }
    return 0;
}

解法2：采用归并排序求解，复杂度nlgn

代码语言：javascript复制

#include<iostream>
#include<cstring>
using namespace std;
int sum=0;
void merge(int *arr,size_t left,size_t mid,size_t right)
{
    int len = right - left   1;
    int *temp = new int [len];  //数组较长时请用new，不然栈空间容易溢出
    size_t index = 0;
    size_t i = left, j = mid   1;
    while(i <= mid && j <= right)
    {
        if(arr[i]<=arr[j])
        {
            temp[index  ] = arr[i  ];
        }
        else
        {
            temp[index  ] = arr[j  ];
            sum  = mid - i   1;       //左边数比右边大，那么左边剩余的也比其大！！！！！！！！！！
        }
        //对两边的数组从小到大放入临时空间
    }
    while(i <= mid)     //比较完后，左半边有没放进去的，直接写入
    {
        temp[index  ]= arr[i  ];
    }
    while(j <= right)   //比较完后，右半边有没有放进去的，直接写入
    {
        temp[index  ]= arr[j  ];
    }
    for(int k = 0;k< len;  k)
    {
        arr[left   ]= temp[k];  //把有序的临时数组写入原来数组的起始位置
    }
    delete [] temp;  //释放空间
    temp = NULL;  //指针置空
}
void divide(int *arr,size_t left,size_t right)
{
    if(left == right)
    {   
        return;
    }
    size_t mid = (left right)/2;  //找出区间中部的数，将数组分段
    divide(arr,left,mid);  //递归调用，对左边继续分段；
    divide(arr,mid 1,right);  //递归调用，对右边继续分段；
    merge(arr,left,mid,right); //对左右两半进行排序合并成一小段有序的数组
}
void mergesort(size_t dsize, int *arr)
{
    if(dsize <= 1)  //预防特殊情况下后面代码失效
    {
        return;
    }
    size_t left = 0, right = dsize-1;
    divide(arr,left,right);
}

int main()
{
    const int N = 1001;
    int cyctime,len,len1;
    int arr[N];
    int i=0,j=0,temp;
    memset(arr,0,sizeof(int)*N);
    cin >> cyctime;
    for(i = 0; i < cyctime;   i)
    {
        //cin.clear();
        cin >> len;
        len1=len;
        j=0;
        while(len1--)	//先输入数组
        {
            cin >> temp;
            arr[j  ] = temp;
        }
        mergesort(len,arr);
        cout << "Scenario #" << i 1 << ":" << endl;
        cout << sum << endl << endl;
        sum = 0;
    }
    return 0;
}

由上可看出归并排序求解时间效率更高。

排序 效率

0 人点赞