js实现查找逆序数
查找逆序数的实现方法
逆序数（Inversion Count）用于衡量一个数组或序列的排序程度。逆序数定义为数组中满足 i < j 且 arr[i] > arr[j] 的元素对数。以下是几种常见的实现方法：
暴力法
直接遍历所有可能的元素对，统计逆序数。时间复杂度为 O(n²)，适用于小规模数据。
function countInversionsBruteForce(arr) {
let count = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) count++;
}
}
return count;
}归并排序法
利用归并排序的分治思想，在合并过程中统计逆序数。时间复杂度为 O(n log n)，适合大规模数据。
function countInversionsMergeSort(arr) {
function mergeAndCount(arr, left, mid, right) {
const temp = [];
let i = left, j = mid + 1, count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push(arr[i++]);
} else {
temp.push(arr[j++]);
count += mid - i + 1;
}
}
while (i <= mid) temp.push(arr[i++]);
while (j <= right) temp.push(arr[j++]);
for (let k = left; k <= right; k++) arr[k] = temp[k - left];
return count;
}
function mergeSortAndCount(arr, left, right) {
let count = 0;
if (left < right) {
const mid = Math.floor((left + right) / 2);
count += mergeSortAndCount(arr, left, mid);
count += mergeSortAndCount(arr, mid + 1, right);
count += mergeAndCount(arr, left, mid, right);
}
return count;
}
return mergeSortAndCount(arr, 0, arr.length - 1);
}使用二叉索引树（Fenwick Tree）
通过动态维护前缀和的方式统计逆序数。时间复杂度为 O(n log n)，但需要离散化数据。
function countInversionsFenwickTree(arr) {
const unique = [...new Set(arr)].sort((a, b) => a - b);
const rank = (x) => unique.indexOf(x) + 1;
const fenwick = new Array(unique.length + 1).fill(0);
function update(index, delta) {
while (index < fenwick.length) {
fenwick[index] += delta;
index += index & -index;
}
}
function query(index) {
let sum = 0;
while (index > 0) {
sum += fenwick[index];
index -= index & -index;
}
return sum;
}
let count = 0;
for (let i = arr.length - 1; i >= 0; i--) {
const r = rank(arr[i]);
count += query(r - 1);
update(r, 1);
}
return count;
}方法对比
- 暴力法：实现简单，但性能较差，适用于小数据量。
- 归并排序法：高效且稳定，适合大规模数据。
- Fenwick Tree：适用于需要动态维护的场景，但实现较复杂。
根据实际需求选择合适的方法即可。
