matlab - 在 MATLAB 中使用 MergeSort 计算倒数

Question

我正在尝试使用 MergeSort 在 MATLAB 中实现反转计数器，但由于某种原因，有些答案离题了。例如，[3, 4, 8, 1] 中的反转数为 3，但我得到 2。但是，数组的排序正确，所以我认为我计算拆分反转的方式是问题所在。

这是我的代码：

function [count, sorted] = mergesort(A)
% count is the number of inversions; sorted is the sorted array.

n = length(A);
if n == 1
    count = 0;
    sorted = A;
else
    m = ceil(n/2);
    [count1, sorted1] = mergesort(A(1:m));
    [count2, sorted2] = mergesort(A(m+1:n));
    [crosscount, sorted] = merge(sorted1, sorted2);
    count = count1 + count2 + crosscount;
end
end

function [crosscount, z] = merge(x, y)

n = length(x); m = length(y); z = zeros(1, n+m);
ix = 1;
iy = 1;
crosscount = 0;
for iz = 1:(n+m);
    if ix > n
        z(iz) = y(iy);
        iy = iy + 1;
    elseif iy > m
        z(iz) = x(ix);
        ix = ix + 1;
        crosscount = crosscount + (n + 1 - ix); %this might be wrong
    elseif x(ix) <= y(iy)
        z(iz) = x(ix);
        ix = ix + 1;
    elseif x(ix) > y(iy)
        z(iz) = y(iy);
        iy = iy + 1;
        crosscount = crosscount + 1; %im pretty sure this is right
    end
end
end

Answer 1

好的，所以朋友帮我解决了。我的直觉是正确的，但我需要一位实际程序员的帮助来了解我哪里出错了：

elseif iy > m
        z(iz) = x(ix);
        ix = ix + 1;
        crosscount = crosscount + (n + 1 - ix); **%this might be wrong - this is actually wrong, since you don't want to count if you're traversing beyond the edge of the right array, and since the actual counting is happening in the last if case**
    elseif x(ix) <= y(iy)
        z(iz) = x(ix);
        ix = ix + 1;
    elseif x(ix) > y(iy)
        z(iz) = y(iy);
        iy = iy + 1;
        crosscount = crosscount + **(n + 1 - ix)** **this is right because you're counting the remaining numbers in your left array that are also greater than y(iy) and just adding that to your count**
    end