0

在 Hoare 算法的规范实现中，我们需要数组的开始和结束元素作为参数，并且算法为分区数组的开始和结束维护几个标志。以下是我发现的一些标准实现：QuickSort and Hoare Partition Hoare Partition Correctness in java

现在，我做了以下操作，并用一些随机数组对其进行了测试。我不太确定我是否做错了什么——这个实现中是否有任何漏洞？直觉上感觉它与上面的实现非常相似，除了它需要更少的参数。与标准实现相比，它是否具有更好/更差的性能（甚至略微如此）？（尽管，是的，这两个都是 O(n)）

(MATLAB)

function partition(m_input)
pivot = m_input(1);
size = length(m_input);
flag = 1; 
k = 1;
    while(k<=size)
        if(m_input(k)>pivot)
            swap(m_input(size), m_input(k))
            size = size-1;
        else
            swap(m_input(k), m_input(flag))
            flag =k; 
            k=k+1;
        end
     end
end

编辑：输入更改为m_input。

4

1 回答 1

0

我总是更喜欢标准的 Hoare 实现。如果你看它，它不是很直观，但它有一个明显的优势：交换次数更少。虽然您的实现总是有效地进行 N 次比较和 N 次交换，但 Hoare 的实现仅进行 N 次比较，但如果不需要，它不会交换任何内容。

在某些情况下，差异很大。首先，在您使用的环境中，变量/对象的交换或分配是一项昂贵的操作。例如，如果您将 C/C++ 与对象数组一起使用。另一个典型的例子是，如果数组中的许多项具有相同的值，或者当数组几乎已排序并且只需要交换一些项时，Hoare 的分区实现会执行得更好。在这种情况下，Hoare 的版本几乎不执行任何交换，而您的版本仍然需要交换 N 个项目，这需要 N*3 分配指令。

于 2014-04-12T00:06:26.420 回答