小编dra*_*mer的帖子

我正在阅读Robert Sedgewick的“算法”书并完成练习，以提高我的算法知识。我遇到一个困难：

对于长度为N的数组，在Quick.sort（）执行期间最大项可以交换的最大次数是多少？

我已经通过实验确定floor(N/2)，假设数组中的所有元素都是不同的，则最大项的最大交换数为。如何数学证明呢？如果我错了，那我怎么了？

我发现了这个问题的一些提及（例如this），但是答案与我的结果不符。该答案表明最大数量为N-1，但是我找不到这样的数组N-1，当使用我的quicksort版本对它进行排序时，这将使我能够准确交换其最大项目（请参见下文）。

我使用的quicksort代码：

template<typename BiDirIterator, typename Compare = std::less<typename BiDirIterator::value_type>>
BiDirIterator partition(BiDirIterator begin, BiDirIterator end, Compare compare = Compare())
{
    auto partition_item = begin;
    while (true)
    {
        while (++begin != end && !compare(*partition_item, *begin));
        while (begin != end && !compare(*--end, *partition_item));

        if (begin == end)
            break;

        std::iter_swap(begin, end);
    }

    if (partition_item != --begin)
        std::iter_swap(partition_item, begin);

    return begin;
}

template<typename BiDirIterator, typename Compare = std::less<typename BiDirIterator::value_type>>
void …