我正在通过阅读 Robert Sedgewick 的《算法》一书并完成练习来提高我的算法知识。我遇到了困难：
Quick.sort() 执行的最大次数是多少 最大的项可以交换为长度为 N 的数组？
我通过实验确定，假设数组中的所有元素都是不同的，最大项的最大交换次数是
floor(N/2)我发现多次提到这个问题（例如这个），但是答案与我的结果不符。该答案表明最大数量是
N-1N-1我使用的快速排序代码：
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 quicksort(BiDirIterator begin, BiDirIterator end, Compare compare = Compare())
{
if (begin == end || std::next(begin) == end)
return;
auto pos = partition(begin, end, compare);
quicksort(begin, pos, compare);
quicksort(++pos, end, compare);
}
以及我用来计算最后一件商品的交换次数的代码：
struct exchange_counter
{
exchange_counter(int value)
: value(value)
{
}
int value;
int number_of_exchanges = 0;
exchange_counter(const exchange_counter& other) = default;
exchange_counter& operator=(const exchange_counter& other) = default;
exchange_counter(exchange_counter&& other) = default;
exchange_counter& operator=(exchange_counter&& other)
{
value = other.value;
number_of_exchanges = other.number_of_exchanges + 1;
return *this;
}
friend bool operator<(const exchange_counter& left, const exchange_counter& right) noexcept
{
return left.value < right.value;
}
friend bool operator==(const exchange_counter& left, const exchange_counter& right) noexcept
{
return left.value == right.value;
}
};
for (int i = 1; i != 15; ++i)
{
std::vector<exchange_counter> values;
for (int j = 0; j != i; ++j)
values.emplace_back(j);
auto max_element = i - 1;
auto max_number_of_exchanges = 0;
do
{
for (auto& value : values)
value.number_of_exchanges = 0;
auto copy = values;
quicksort(copy.begin(), copy.end());
max_number_of_exchanges = (std::max)(max_number_of_exchanges,
std::find(copy.begin(), copy.end(), max_element)->number_of_exchanges);
}
while (std::next_permutation(values.begin(), values.end()));
std::cout << "Elements: " << i << "; max exchanges: " << max_number_of_exchanges << std::endl;
}
PS。如果我使用相同的方法在 Visual Studio 2015（以快速排序实现）中测试
std::sortN - 1每次对数组进行分区时，最大的项必须移动 2 个位置，以便交换它的次数达到最大。它不能仅移动 1 个位置，因为在这种情况下，它将成为枢轴元素，并将移动到其最终位置。例如，考虑以下数组：
4 10 3 x x x ...
P i j
对数组进行分区后，最大元素（10）向右移动 1 个位置
3 4 10 x x x ...
P
但是现在最大的项成为枢轴元素，并将被移动到数组的末尾，仅添加 1 个交换。
相反，我们需要排列项目，使最大的项目移动 2 个位置，同时保持 1 个项目在前面，成为枢轴元素：
2 10 4 1 x x x ...
P i j
分区后：
1 2 4 10 x x x ...
P i j
最大的物品每次移动2个位置，因此交换次数为floor(N/2)。
示例（N = 10）
2 10 4 1 6 3 8 5 7 9
在此情况下，最大物品（10）的最大交换次数为 5 次。
您对问题的回答不准确。最大数字传递的次数不能超过可用空间的次数，因为它应该始终接近其正确的位置。所以，从第一个到最后一个价值点，它会被交换N次。 这种情况有一个例外，即当数组大小为 1 时，最大元素无法再移动，因此最大移动次数为 N - 1。
这个答案之前已经在这里提供过：选择排序、插入排序和快速排序的场景
这是我的证明：这里
答案是：楼层(N/2)
使用数学归纳法，我们可以发现我们需要一个像这样的序列：
a(k+1) max a(k+3) a(k) ......
每次我们调用分区时，最大元素都会交换一次。
因为 a(k+1) 是枢轴，我们每次都必须将 max 与 a(k) 交换。
每个子数组都必须有这样的序列。这样我们就可以得到楼层(N/2)。
假设有仓库 a，其中元素 $a_k > a_{k-1} (k \in Z)$ 和 $max > a_k$
对于交换元素，只有两种可能：(基于algs4的快速排序的代码)
考虑 N = 4 的情况：
可以构造 $a_2,max,a_1,a_3$
$a_2$作为枢轴，接下来要交换$max$和$a1$
得到：$a_2,a_1,max,a_3$
然后将枢轴放在正确的位置：
$a_1,a_2,最大,a_3$
接下来要对$max,a_3$重新进行划分
最终得到：$a_1,a_2,a_3,max$
可见，$max$交换了2次。
把 N = 4 作为 N = 4 + 2 = 6 的子数列
必然有N = 6 数列划分后的结果：
分区后：$a_{-1},a_0,a_2,max,a_1,a_3$
很容易得到 N = 6 数列在划分前的序列：
分区前：$a_0,max,a_2,a_{-1},a_1,a_3$
其次，N = 6 的数列，要对 max 元素进行 1 + 2 = 3 次交换，其中 2 次是 N = 4 子数列交换的次数。
考虑N = 6 + 2 = 8的数列，N = 6作为其右子数列，容易得到划分前：
分区前：$a_{-2},max,a_0,a_{-3},a_2,a_{-1},a_1,a_3$
相反，将要对max元素进行 1 + 1 + 2 = 4 次交换
由数学归纳法可以发现，N个阵列的阵列，只需满足
$a_{k+1},max,a_{k+3},a_k,......$
即可每次分区都交换一次max
考虑到奇数长度
最终得到结果：N/2收拾整，朴地板(N/2)