使用具有O(NlgN)时间和O(lgN)空间的双向迭代器实现快速排序似乎非常简单。那么，std::sort()需要随机访问迭代器的特殊原因是什么？我已阅读有关该主题的文章whydostd::sortandpartial_sortrequirerandom-accessiterators?.但它没有解释可能的std::sort()实现的具体部分可能实际上需要随机访问迭代器来维持其时间和空间复杂度。O(NlgN)时间和O(lgN)空间的可能实现:templateBidirItpartition(BidirItfirst,BidirItlast,Predpred){while(true){w