js实现查找逆序数
逆序数简介
逆序数指在一个序列中，前面的元素大于后面的元素的对数。例如序列 [2, 4, 1, 3, 5] 的逆序数为 3（即 (2,1), (4,1), (4,3)）。
暴力法实现
直接遍历所有可能的元素对，统计逆序数。时间复杂度为 $O(n^2)$，适用于小规模数据。
function countInversions(arr) {
let count = 0;
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) count++;
}
}
return count;
}
// 示例
console.log(countInversions([2, 4, 1, 3, 5])); // 输出 3归并排序优化法
利用归并排序的分治思想，在合并过程中统计逆序数。时间复杂度为 $O(n \log n)$，适合大规模数据。
function countInversions(arr) {
return mergeSortAndCount(arr, 0, arr.length - 1);
}
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;
}
function mergeAndCount(arr, left, mid, right) {
const temp = [];
let i = left, j = mid + 1, k = 0, count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i + 1); // 统计逆序数
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (let p = 0; p < k; p++) arr[left + p] = temp[p];
return count;
}
// 示例
console.log(countInversions([2, 4, 1, 3, 5])); // 输出 3注意事项
- 暴力法简单直观，但性能较差。
- 归并排序法效率更高，但实现稍复杂。
- 若需处理浮点数或自定义比较逻辑，需调整比较条件（如将
arr[i] <= arr[j]改为自定义函数）。
