超快速排序

题目 超快速排序

image-ad001db6

思路分析

思路同逆序对数量

也是归并过程中的子问题

实际就是算出现了多少次j在i先放入数组

这是一类问题 比如冒泡排序是基于交换 至于到底需要交换多少次 我们就可以通过使用效率更高的归并排序求出逆序对数量 从而得知冒泡排序需要交换多少次

代码实现

 #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500100;
LL q[N];
LL cnt;

void merge_sort(LL q[],LL l,LL r)
{
    if(l>=r)
        return;

    LL mid=l+r>>1;
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);

    LL k=0,i=l,j=mid+1,tmp[r-l+1];
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j])
            tmp[k++]=q[i++];
        else
        {
            tmp[k++]=q[j++];
            cnt+=mid-i+1;
        }
    }
    while(i<=mid)
        tmp[k++]=q[i++];
    while(j<=r)
        tmp[k++]=q[j++];
    for(i=l,k=0;i<=r;i++,k++)
        q[i]=tmp[k];
}

int main()
{
    LL n;
    while(cin>>n && n)
    {
        for(LL i=0;i<n;++i)
        {
            scanf("%d",&q[i]);
        }
        cnt=0;
        merge_sort(q,0,n-1);
        cout<<cnt<<endl;
    }
    return 0;
}

同类题型

视频讲解

⬅️ 逆序对的数量 🏠 00-听课板子 ➡️ 二分