一個(gè)區(qū)間的逆序?qū)?shù)=左邊逆序?qū)Φ臄?shù)+右邊逆序?qū)Φ臄?shù)+跨邊界的逆序?qū)?shù)。

其實(shí)就是在歸并過(guò)程中，如果有的某一個(gè)數(shù)大于左邊的一個(gè)數(shù)，就把左邊遍歷到的數(shù)字?jǐn)?shù)量加上。因?yàn)樽筮吺怯行虻?，只要右邊的?shù)大于左邊的一個(gè)數(shù)，就會(huì)大于左邊那個(gè)數(shù)前面所有的數(shù)

平均時(shí)間復(fù)雜度為O(nlogn)。

歸并排序求逆序?qū)Φ倪^(guò)程

1. 遞歸左區(qū)間，計(jì)算左邊逆序?qū)Φ臄?shù)

2. 遞歸右區(qū)間，計(jì)算右邊逆序?qū)Φ臄?shù)

3. 循環(huán)比較左右區(qū)間，計(jì)算跨邊界的逆序?qū)?shù)

4. 歸并

而對(duì)于跨邊界的逆序?qū)?shù)量，由歸并排序的特點(diǎn)可知第三種情況的個(gè)數(shù)為當(dāng)數(shù)組[i] > 數(shù)組[j] 時(shí)，i后面的所有數(shù)都大于數(shù)組[j]即個(gè)數(shù)為mid - i + 1。

感嘆，歸并真的神奇。

夕弦的圖片由NovelAI生成， 練了個(gè)新模型，但似乎效果和up紅心咖啡_Official的差不多