#1 #2 WA

#3 #4 AC

#5 TLE

template<typename Iterator>
    void SortNoRecursion(Iterator begin, Iterator end, bool choose) {
        using value_type = typename std::iterator_traits<Iterator>::value_type;
        using difference_type = typename std::iterator_traits<Iterator>::difference_type;

        auto len = std::distance(begin, end);
        if (len <= 1) return;

        std::stack<std::pair<Iterator, Iterator>> range;
        range.push({begin, end});
        if (choose) {
            while (!range.empty()) {
                auto [left, right] = range.top();
                auto it=range.top();
                range.pop();
                auto len = std::distance(left, right);
                --right;
                if (len <= 1) continue;
                auto pivot = std::next(left, randint((difference_type) 0, len - 1));//随机分界值
                while (left != right) {
                    while (*left < *pivot && left < right) ++left;
                    while (*right >= *pivot && left < right) --right;//上面为什么right要自己减的原因
                    std::swap(*left, *right);
                }
                if (*left >= *pivot) std::swap(*left,*pivot);
                else ++left;
                range.push({it.first,left});
                range.push({left+1,it.second});
            }
        }
    }

调用这个函数就传入一个容器的begin和end的，左闭右开