什么是逆序數(shù)，可不可以舉個例子

如2431中，21，43，41，31是逆序，逆序數(shù)是4，為偶排列。

在一個排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序。一個排列中逆序的總數(shù)就稱為這個排列的逆序數(shù)。也就是說，對于n個不同的元素，先規(guī)定各元素之間有一個標(biāo)準(zhǔn)次序（例如n個 不同的自然數(shù)，可規(guī)定從小到大為標(biāo)準(zhǔn)次序）。

歸并排序

直接計數(shù)法雖然簡單直觀，但是其時間復(fù)雜度是 O(n^2)。一個更快（但稍復(fù)雜）的計算方法是在歸并排序的同時計算逆序數(shù)。

下面這個 C++ 編寫的例子演示了計算方法。函數(shù) mergeSort() 返回序列的逆序數(shù)。

int is1[n],is2[n];// is1為原數(shù)組，is2為臨時數(shù)組，n為個人定義的長度。