我正在通过阅读 Robert Sedgewick 的“算法”一书并完成练习来提高我的算法知识。这是我遇到的困难:
What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N ?
我已经通过实验确定,最大项目的最大交换次数是 floor(N/2)
,假设数组中的所有元素都是不同的。 我如何从数学上证明这一点?如果我错了,我的错是什么?
我发现有好几处提到了这个问题(例如 this one ),但是,答案与我的结果不符。这个答案表明最大数量是 N-1
,但是 我找不到这样的数组,它会给我正好 N-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;
}
附言。如果我使用相同的方法在 Visual Studio 2015(实现为快速排序)中测试 std::sort
,则最大项的交换次数为 N - 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。
关于c++ - 快速排序的最大元素交换次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43263249/