最少的交换...找逆序对题解

这个找逆序对的题真的搞了我很久,明明题目理解起来一点都不复杂嘤嘤嘤.最开始直接用冒泡,哈哈哈哈太天真了,后来改用插入排序,明明是和冒泡同样的复杂度......都是o(N^2),最后终于用了归并,复杂度是nlogn
原理早就弄懂了,但小细节没有处理好,一直是输出错误50%,我的天哪,终于做出来了,和其他博主的长篇大论比起来,这差不多是最简洁的代码了.先上题:

问题 D: 最少的交换

时间限制: 1 Sec 内存限制: 32 MB

题目描述

现在给你一个由n个互不相同的整数组成的序列，现在要求你任意交换相邻的两个数字，使序列成为升序序列，请问最少的交换次数是多少？

输入

输入包含多组测试数据。每组输入第一行是一个正整数n（n<500000），表示序列的长度，当n=0时。
接下来的n行，每行一个整数a[i]（0<=a[i]<=999999999），表示序列中第i个元素。

输出

对于每组输入，输出使得所给序列升序的最少交换次数。

样例输入

9
1
0
5
4
3
1
2
3
0

样例输出

6
0

#include<cstdio>
#include<iostream>
using namespace std;
void msort(int begin, int end, long long &ans, int* a, int* c )//归并排序
{
    if (begin == end)    //左边和右边相等就return
        return;
    int mid = (begin + end) / 2;
        int i = begin;    //用来记录左半边数组的下标
        int j = mid + 1;    //用来记录右半边数组的下标
        int k = begin;    //用来指向临时放入那个数组
    msort(begin, mid,ans,a,c), msort(mid + 1, end,ans,a,c);
    while (i <= mid && j <= end)    //右半边和左半边都还没有遍历完
        if (a[i] <= a[j])
            c[k++] = a[i++];
        else
            c[k++] = a[j++], ans += mid - i + 1;   
/*统计答案,右边数组中还没有放进去的都是逆序*/
    while (i <= mid)    //把最后剩下的加上
        c[k++] = a[i++];
    while (j <= end)
        c[k++] = a[j++];
    for (int l = begin; l <= end; l++)   //再放回a
        a[l] = c[l];
}

int main()
{
    int n;
    while (1)
    {
        cin >> n;
        if (n == 0)
            break;
        int* a = new int[n];    //输入放在a里
        int* c = new int[n];    //c是用来辅助排序的
/*最开始开辟临时数组会比在函数里临时开辟节省开销,具体见MOOC浙大数据结构归并排序,姥姥有讲过*/
        for (int i = 1; i <= n; i++)
            cin >> a[i];
/*在最前面全局定义a[n]和c[n]还有ans很容易出问题,所以最好还是每次重新开辟数组比较保险.*/
        long long ans = 0;
        msort(1, n,ans,a,c);
        cout << ans << endl;
    }
    return 0;
}

归并排序用到了二分的思想，在排序过程中如果a[i]<=a[j]就不会产生逆序对，如果a[i]>a[j]就会产生mid−i+1个逆序对，因为做归排的时候l～mid和mid+1～r都是已经排好序的所以如果a[i]>a[j]那么a[i+1]～a[mid]也就都大于a[j]

洛谷上也有题解:
https://www.luogu.org/problemnew/solution/P1908
姥姥的归并课程:
https://www.icourse163.org/learn/ZJU-93001?tid=1003997005#/learn/content?type=detail&id=1007588513

一定要牢记各种排序的时间复杂度,就不会出现用插入换冒泡结果复杂度相同的尴尬场景了

//错误：时间超限百分之50,用简单选择排序

#include <iostream>
#include<vector>
using namespace std;

void judge(int n)
{
    vector<int>array;
    for (int i = 0; i < n; i++)
    {
        int b;
        cin >> b;       //每个数字
        array.push_back(b);
    }
    int total = 0;
    for (int i = 0; i < n; i++)     //选择排序执行n次
    {
        int max = -1, keep = 0;    
        int j = 0;
        for (; j < n - i; j++)      //每次从从后往前推一个字
            if (max < array[j])
            {
                max = array[j];
                keep = j;
            }
        if (j != n - i - 1)     //如果最大的不是最后一个就交换
        {
            total += n - i - keep - 1;      //从keep移动到n-i-1这个位置(下标),移动了这些步
            array.erase(array.begin() + keep);
            if (i == 0)
                array.push_back(max);
            if (i != 0)
                array.insert(array.begin() + n - i - keep,1, max);
        }
    }
    cout << total << endl;
}


int main()
{
    int n;      //
    while (1)
    {
        cin >> n;
        if (n == 0)
            break;
        judge(n);
    }
    return 0;
}