求序列逆序數(shù)

整體思路是用到分治的思想，其實(shí)該問(wèn)題可以在歸并排序過(guò)程中解決，因此該題代碼只需要在歸并排序代碼上增加一個(gè)變量記錄逆序數(shù)即可，但正如那個(gè)修機(jī)器的故事一樣，換釘子不難，但知道在哪里換釘子卻是非常關(guān)鍵。
代碼如下，只是在歸并排序的基礎(chǔ)上增加了一個(gè)記錄逆序數(shù)的地方
void reverse(int num[],int left,int right)//跟歸并排序一樣
{
int mid;
if(right-left+1>1)//當(dāng)序列長(zhǎng)度大于一時(shí)，分成兩半進(jìn)行歸并
{
mid= (left+right)/2
reverse(num,left,mid);
reverse(num,mid+1,right);
merge(num,left,right,(left+right)/2);
}
}
void merge(int a[],int left,int right,int mid)//歸并過(guò)程
{
int i,j,k;
int temp[right-left+1];
for(i=left,j=mid+1,k=0;k<right-left+1;k++)
{
if(a[i]<=a[j]&&i<mid+1)
{
temp[k]=a[i++];
}
else if(a[i]>a[j]&&j<=right)
{
temp[k]=a[j++];
cnt+=mid-i+1;//逆序數(shù)增加，增加數(shù)為前序列的剩余項(xiàng)
}
else if(i==mid+1)
{
temp[k]=a[j++];
}
else if(j>right)
{
temp[k]=a[i++];
}

}
for(i=0;i<right-left+1;i++)
{
a[left+i]=temp[i];
}

}
兩個(gè)有序序列，在歸并比較過(guò)程中，如果后序列元素小，說(shuō)明前序列包括當(dāng)前項(xiàng)在內(nèi)的剩余項(xiàng)均大于后序列的當(dāng)前項(xiàng)，此時(shí)逆序數(shù)就增加了前序列的剩余項(xiàng)數(shù)。

需要理解的一點(diǎn)時(shí)，歸并排序過(guò)程中，當(dāng)二分到長(zhǎng)度只有一時(shí)，序列就是有序的了，然后再進(jìn)行歸并，產(chǎn)生更長(zhǎng)的有序序列。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

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

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