1

我在 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) = [];可能会消耗大量时间。但是当我将 in 更改[]为-999（低于输入向量的任何数量）时，它无济于事，反而花费了更多时间。

4

1 回答 1

4

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

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

一个简单的测试：

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

用于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. 这部分是因为我想给你一个好的建议，部分是为了避免被提醒不要在 MATLAB 中使用iandj作为变量。

于 2016-02-08T07:08:31.743 回答