的快速排序

Question

最大元素交流的数量，我提高我的算法知识读本罗伯特·塞奇威克“算法”一书，并完成练习。还有一个我有困难：

什么是Quick.sort（） 的执行，最大的项目，可以更换，长度为N的数组中的最大次数？

我已通过实验确定，假设数组中的所有元素都不相同，最大项目的最大交换次数为floor(N/2)。 如何在数学上证明这一点？如果我错了，我的错误是什么？

我发现了几个提到的这个问题（如this one），但是，答案与我的结果不符。那答案建议的最大数量是N-1，但我没能找到这样的阵列，这将使我的最大项目的确切N-1交流，用我的快速排序版本（见下文）排序时。

快速排序的代码，我使用：我用来计算交流为lasgest项目的编号

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::sort，最大项的交换次数为N - 1。

Answer 1

最大的项目必须按每次2个位置移动，我们以交换它的最大次数的阵列分区。它不能被移动一个位置，因为在这种情况下，它将成为一个枢轴元素，并将移动到其最终位置。例如，考虑下面的数组：

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在这种情况下。

Answer 2

您的问题的答案是不准确的。最大数量不能超过可用空间的次数，因为它应该始终接近正确的位置。因此，从第一个值到最后一个值点，它将被交换N次。 对于这种情况有一个排除，那就是当数组大小为1时，最大的元素不能再移动，因此最大移动次数将为N-1。

此答案是在此之前已经提供：Scenarios for selection sort, insertion sort, and quick sort