分別將每個元素和其后面的所有元素進行逐個比較

• if 后面有比其小的元素: 逆序?qū)?shù)量++
• 重復(fù)直至最后一個元素

核心代碼

// 暴力解決策略的核心代碼
int count = 0;
for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (a[i] > a[j]) {count++;}}
}

復(fù)雜度分析
需要使用兩個for循環(huán)——$O(n^2)$

復(fù)雜度較高，在一些要求較高的情況下會報超時錯誤

小挑戰(zhàn)：你能嘗試用暴力解法解決這個問題嗎？試試看，感受一下它的時間復(fù)雜度吧！😉

2. 策略②：運用「歸并排序」的算法思想 🧠

（1）回顧「歸并排序」算法原理

（2）改動以求逆序?qū)?shù)量

原理分析
在歸并排序的過程中，當我們合并兩個有序的子數(shù)組時，如果左邊的某個元素 a[i] 大于右邊的某個元素 a[j]，那么 a[i] 和 a[j] 就構(gòu)成了一個逆序?qū)?。不僅如此，由于左邊的子數(shù)組是有序的，a[i] 后面的所有元素也都大于 a[j]，因此我們可以一次性計算出多個逆序?qū)Α?/p>

代碼實現(xiàn)

#include <iostream>using namespace std;typedef long long LL; // 結(jié)果較大const int N = 100010;
int n;
int a[N], temp[N];// 求逆序?qū)?shù)量
LL rev_pair(int a[], int l, int r)
{if (l >= r)return 0;int mid = l + r >> 1;LL res = rev_pair(a, l, mid) + rev_pair(a, mid + 1, r);int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r){if (a[i] <= a[j])temp[k++] = a[i++];else{temp[k++] = a[j++];// 當a[i]>a[j]時，對于a[j]：與[i, mid]區(qū)間內(nèi)的元素可組成逆序?qū)?/span>res += mid - i + 1;}}while (i <= mid)temp[k++] = a[i++];while (j <= r)temp[k++] = a[j++];for (int i = l, j = 0; i <= r; ++i, ++j)a[i] = temp[j];return res;
}int main()
{cin >> n;for (int i = 0; i < n; ++i)cin >> a[i];LL res = rev_pair(a, 0, n - 1);cout << res << endl;return 0;
}

復(fù)雜度分析
歸并排序的時間復(fù)雜度是 $O(n\log n)$，因此這個解法的時間復(fù)雜度也是 $O(n\log n)$，比暴力解法高效得多。

學(xué)習(xí)建議和鼓勵 🌟

1. 多動手實踐：算法的學(xué)習(xí)離不開實踐，建議你親自編寫代碼并運行，感受算法的魅力。
2. 不要害怕挑戰(zhàn)：算法的學(xué)習(xí)過程中難免會遇到困難，但每一次克服困難都是一次成長。💪
3. 多與他人交流：加入一些算法學(xué)習(xí)群，和志同道合的小伙伴一起討論問題，互相學(xué)習(xí)。

互動性元素 🎉

小挑戰(zhàn)：你能嘗試用歸并排序的思想解決其他問題嗎？比如求一個數(shù)組中的順序?qū)?/strong>數(shù)量？🤔