【概述】

設(shè)A為一個(gè)有n個(gè)數(shù)字的有序集，其中所有數(shù)字各不相同。如果存在整數(shù)i、j，使得1<=i<j<=n且A[i]>A[j]，則{A[i],A[j]}這個(gè)有序?qū)ΨQ為A的一個(gè)逆序?qū)Α?/p>

例如：集合{3,1,4,5,2}的逆序?qū)τ衶3,1}、{3,2}、{4,2}、{5,2}共4個(gè)。

而逆序?qū)?wèn)題，即：對(duì)給定的數(shù)組序列，求其逆序?qū)Φ臄?shù)量。

【分析】

從定義上分析，逆序?qū)褪菙?shù)列中任意兩個(gè)數(shù)滿足大的在前，小的在后的組合。如果將這些逆序?qū)Χ颊{(diào)整為順序，那么整個(gè)數(shù)列就變的有序，即排序。

因而容易想到冒泡排序的機(jī)制正好是利用消除逆序來(lái)實(shí)現(xiàn)的，也就是說(shuō)，交換相鄰兩個(gè)逆序數(shù)，最終實(shí)現(xiàn)整個(gè)序列有序，那么交換的次數(shù)即為逆序?qū)Φ臄?shù)量。

但由于冒泡排序本身效率不高，時(shí)間復(fù)雜度為O（n^2），對(duì)于n較大的情況下不適用，因此我們用歸并排序來(lái)解決逆序?qū)?wèn)題。

【程序?qū)崿F(xiàn)】

/*只需修改原有歸并程序，當(dāng)右邊序列元素為較小值時(shí)，就統(tǒng)計(jì)其產(chǎn)生的逆序?qū)?shù)量，即可完成逆序?qū)y(tǒng)計(jì)*/ void msort(int s,int t) {if(s==t)//只有一個(gè)數(shù)字則返回return;int mid=(s+t)/2;msort(s,mid);//分解左序列msort(mid+1,t);//分解右序列int i=s,j=mid+1,k=s;while(i<=mid&&j<=t){if(a[i]<=a[j]){r[k]=a[j];k++;i++;}else{r[k]=a[j];k++;j++;ans+=mid-i+1;//統(tǒng)計(jì)產(chǎn)生逆序?qū)Φ臄?shù)量}}while(i<=mid){//復(fù)制左邊子序列剩余r[k]=a[i];k++;i++;}while(j<=t){//復(fù)制右邊子序列剩余r[k]=a[j];k++;j++;}for(i=s;i<=t;i++)a[i]=r[i]; }

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 排序 —— 逆序对问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。