快速排序实现C++11

Question

下面是使用迭代器的qsort实现，就像在std::sort中一样

// iterator check
template <typename It, typename T>
constexpr bool is = std::is_same<std::iterator_traits<It>::iterator_category, T>::value;


// quick sort
template <typename BidIt, typename Pred>
void qsort(BidIt first, BidIt last, Pred compare) noexcept
{
    static_assert(is<BidIt, std::bidirectional_iterator_tag> || is<BidIt, std::random_access_iterator_tag>,
        "bidirectional iterator required");

    auto size = std::distance(first, last);

    if (size > 1) {
        using content_type = std::iterator_traits<BidIt>::value_type;

        content_type pivot = *first;
        std::vector<content_type> left(size), right(size);
        auto left_end = left.begin();
        auto right_end = right.begin();

        for (BidIt i = std::next(first); i != last; ++i) {
            compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
        }

        qsort(left.begin(), left_end, compare);
        qsort(right.begin(), right_end, compare);

        std::copy(left.begin(), left_end, first);
        *std::next(first, std::distance(left.begin(), left_end)) = pivot;
        std::copy(right.begin(), right_end, std::next(first, std::distance(left.begin(), left_end) + 1));
    }
}

你的想法？

Answer 1

通知1

您可以节省一些缩进空间：

if (size > 1) {
    ... // Lots of code.
}

至

if (size < 2) {
    return;
}
... // Lots of code here.

建议2

您可以就地进行分区；不需要要求更多的内存。维基百科中的伪代码相当详细，不使用任何辅助内存(当然，递归堆栈除外)，并且易于理解。

Answer 2

1. 您忘记指定包含项，因此不会对它们进行仔细检查。你需要<iterator>，<type_traits>和<vector>。我的变更用<vector>换<algorithm>。
2. 检查基类，而不是基类和所有派生类型的详尽列表。
3. 插入typename将相依类型标记为类型。
4. 为模板和函数提供默认参数，以便最大程度地方便和灵活地使用ou。
5. 使用早期返回来完全处理你能立即处理的事情。记住，最重要的资源是读者的有限注意力。
6. 不要把自己限制在可复制的类型上。不复制枢轴的另一个好处是较小的堆栈帧。
7. 避免分配额外的空间，这是昂贵的。这也允许您最小化复制。查看阵列正负数划分的最快算法以获得有效的就地划分范围的方法。
8. 如果排序因任何原因失败，是否确定要中止程序？还是标记函数noexcept有点过了？
9. 获取范围的大小可能是O(n)操作。避免那样做。
10. 如果所有元素相等，则该算法退化为O(n)。

#include <iterator>
#include <type_traits>
#include <algorithm>

// quick sort
template <typename BidIt, typename Pred
    = std::less<typename std::iterator_traits<BidIt>::value_type>>
void qsort(BidIt first, BidIt last, Pred compare = {})
noexcept(noexcept(compare(*first, *first), std::iter_swap(first, first)))
{
    static_assert(std::is_base_of<std::bidirectional_iterator_tag,
        typename std::iterator_traits<BidIt>::iterator_category>(),
        "at least bidirectional iterator required");

    if (first == last || first == last - 1)
        return;

    const auto& pivot = *first;
    auto left = first; ++left;
    auto right = last;

    do {
        do --right;
        while (left != right && !compare(*right, pivot));
        while (left != right && compare(*left, pivot))
            ++left;
        if (left != right) {
            std::iter_swap(left, right);
            ++left;
        }
    } while (left != right);

    std::iter_swap(first, left - 1);

    qsort(first, left - 1, compare);
    qsort(left, last, compare);
}

Answer 3

一般注意：std::sort()实现从libc++到libstdc++各不相同，但一般来说，它们要复杂得多。这个职位对你来说可能很有趣。

Thoughts:

• 这将不适用于非默认的可构造类型(因为left和right构造)。
• 最好将Pred默认为std::less<> (或为C++11键入一个)，并使compare默认为默认构造模板<.，typename Pred = std::less<>> .(.，Pred compare = {}) {.}
• 代码在typename之前需要std::iterator_traits<BidIt>::iterator_category，因为iterator_category是一个依赖类型。
• 错误的措辞应该说“至少”要简明扼要。

使用演示的完整代码：

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <functional>

// iterator check
template <typename It, typename T>
constexpr bool is = std::is_same<typename std::iterator_traits<It>::iterator_category, T>::value;


// quick sort
template <typename BidIt, typename Pred = typename std::less<typename std::iterator_traits<BidIt>::value_type>>
void qsort(BidIt first, BidIt last, Pred compare = {}) noexcept
{
    static_assert(is<BidIt, std::bidirectional_iterator_tag> || is<BidIt, std::random_access_iterator_tag>,
        "at least bidirectional iterator required");

    auto size = std::distance(first, last);

    if (size > 1) {
        using content_type = typename std::iterator_traits<BidIt>::value_type;

        content_type pivot = *first;
        std::vector<content_type> left, right;
        left.reserve(size);
        right.reserve(size);
        auto left_end = std::back_inserter(left);
        auto right_end = std::back_inserter(right);

        for (BidIt i = std::next(first); i != last; ++i) {
            compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
        }

        qsort(left.begin(), left.end(), compare);
        qsort(right.begin(), right.end(), compare);

        std::copy(left.begin(), left.end(), first);
        *std::next(first, std::distance(left.begin(), left.end())) = pivot;
        std::copy(right.begin(), right.end(), std::next(first, std::distance(left.begin(), left.end()) + 1));
    }
}

struct integer
{
    integer() = delete; //not default constructible
    integer(int y):
                x(y)
    {}

    int x;
};

bool operator<(const integer& lhs, const integer& rhs)
{
    return lhs.x < rhs.x;
}

std::ostream& operator<<(std::ostream& os, const integer& x)
{
    os << x.x;
    return os;
}

int main() {
    std::vector<integer> v{1, 0, -1, 4, 2};
    qsort(v.begin(), v.end());
    std::copy(v.begin(), v.end(), std::ostream_iterator<integer>(std::cout, " "));
}