堆排序在 MATLAB 上应该很慢吗？

Question

我在 MATLAB 中写了一个堆排序函数，它工作正常，除了当输入的长度大于或等于 1000 时，它可能需要 很长的时间（例如1000 的长度需要半秒）。我不确定是不是 MATLAB 在堆排序算法上运行不是很快，还是我的代码需要改进。我的代码如下所示：

function b = heapsort(a)

[~,n] = size(a);
b = zeros(1,n);
for i = 1:n
    a = build_max_heap(a);
    b(n+1-i) = a(1);

    temp = a(1);
    a(1) = a(n+1-i);
    a(n+1-i) = temp;

    a(n+1-i) = [];
    a = heapify(a,1);
end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function a = build_max_heap(a)
[~,n] = size(a);
m = floor(n/2);
for i = m:-1:1
    a = heapify(a,i);
end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function a = heapify(a,i)
[~,n] = size(a);

left = 2*i;
right = 2*i + 1;

if left <= n 
    if a(left) >= a(i)
        large = left;
    else
        large = i;
    end
else
    return
end
if right <= n
    if a(right) >= a(large)
        large = right;
    end
end

if large ~= i
    temp = a(large);
    a(large) = a(i);
    a(i) = temp;
    a = heapify(a,large);
end
end

我知道可能是代码 a(n+1-i) = []; 消耗了很多时间。但是，当我将 [] 更改为 -999（低于输入向量的任何数量）时，它并没有帮助，但甚至花费了更多时间。

Answer 1

您应该使用 profiler 来检查哪些行花费的时间最多。肯定是 a(n+1-i) = []; 拖慢了您的功能。

在循环中调整数组大小非常慢，因此您应该始终尽量避免它。

一个简单的测试：

创建一个函数，将一个大向量作为输入，并迭代地删除元素，直到它为空。
创建一个函数，将相同的向量作为输入并迭代地将每个值设置为 0、Inf、NaN 或其他值。

使用timeit检查哪个函数更快。您会看到最后一个函数大约快 100 倍（当然取决于向量的大小）。

之所以-999需要更多的时间，很可能是因为a不再越来越小，因此a = heapify(a,1);不会越来越快。我还没有测试过，但是如果你在你的第一个函数中尝试以下，你可能会得到一个更快的程序（你必须在你的代码中的其他地方也插入 n+1-i)，但我会留下那个给你）：

a(n+1-ii) = NaN;
a(1:n+1-ii) = heapify(a(1:n+1-ii),1);

请注意，我将 i 更改为 ii。这部分是因为我想给你一个好的建议，部分是为了避免被提醒 not use i and j as variables in MATLAB.

堆排序在 MATLAB 上应该很慢吗？

Is heap sort supposed to be very slow on MATLAB?

sorting

algorithm

matlab

heapsort

clrs