最笨的方法时间复杂度为O(n2),采用利用二分归并排序算法思想,时间复杂度为O(nlogn)
#includeusing namespace std; int a[1000], temp[1000]; long long sum = 0; void merge(int a[], int s, int m, int e, int temp[]) { int pb = 0; int p1 = s, p2 = m + 1; while (p1 <= m && p2 <= e) { if (a[p1] < a[p2]) temp[pb++] = a[p1++]; else { temp[pb++] = a[p2++]; sum += (m - p1 + 1); // 关键点 } } while (p1 <= m) temp[pb++] = a[p1++]; while (p2 <= e) temp[pb++] = a[p2++]; for (int i = 0; i < e - s + 1; i++) a[s + i] = temp[i]; } void mergeSortCount(int a[], int s, int e, int temp[]) { if (s < e) { int m = s + (e - s) / 2; mergeSortCount(a, s, m, temp); mergeSortCount(a, m + 1, e, temp); merge(a, s, m, e, temp); } } void main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; mergeSortCount(a, 0, n - 1, temp); /*for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << endl;*/ cout << sum << endl; system("pause"); }