std::forward_list::sort如何在NlogN時間內作業？

我無法想象如何以適當的時間復雜度重新排序單鏈表（圖書館說它需要“大約”NlogN）。有沒有我可以用來查找有關它的教育材料的演算法名稱？sort我查看了標準庫中的代碼，但除了在名為or的少數函式之一的末尾附近發生了合并之外，我想不出太多sort2。下面是一些用到的函式：

    template <class _Pr2>
    static void _Sort(_Nodeptr _BFirst, _Pr2 _Pred) {
        auto _BMid       = _Sort2(_BFirst, _Pred);
        size_type _Bound = 2;
        do {
            if (!_BMid->_Next) {
                return;
            }

            const auto _BLast = _Sort(_BMid, _Bound, _Pred);
            _BMid             = _Inplace_merge(_BFirst, _BMid, _BLast, _Pred);
            _Bound <<= 1;
        } while (_Bound != 0);
    }

    template <class _Pr2>
    static _Nodeptr _Sort(const _Nodeptr _BFirst, size_type _Bound, _Pr2 _Pred) {
        // Sort (_BFirst, _BFirst   _Bound), unless nullptr is encountered.
        // Returns a pointer one before the end of the sorted region.
        if (_Bound <= 2) {
            return _Sort2(_BFirst, _Pred);
        }

        const auto _Half_bound = _Bound / 2;
        const auto _BMid       = _Sort(_BFirst, _Half_bound, _Pred);
        if (!_BMid->_Next) {
            return _BMid;
        }

        const auto _BLast = _Sort(_BMid, _Half_bound, _Pred);
        return _Inplace_merge(_BFirst, _BMid, _BLast, _Pred);
    }

    template <class _Pr2>
    static _Nodeptr _Inplace_merge(_Nodeptr _BFirst1, const _Nodeptr _BMid, const _Nodeptr _BLast, _Pr2 _Pred) {
        // Merge the sorted ranges (_BFirst1, _BMid] and (_BMid, _BLast)
        // Returns one before the new logical end of the range.
        auto _First2 = _BMid->_Next;
        for (;;) { // process 1 splice
            _Nodeptr _First1;
            for (;;) { // advance _BFirst1 over elements already in position
                if (_BFirst1 == _BMid) {
                    return _BLast;
                }

                _First1 = _BFirst1->_Next;
                if (_DEBUG_LT_PRED(_Pred, _First2->_Myval, _First1->_Myval)) {
                    // _First2->_Myval is out of order
                    break;
                }

                // _First1->_Myval is already in position; advance
                _BFirst1 = _First1;
            }

            // find the end of the "run" of elements less than _First1->_Myval in the 2nd range
            auto _BRun_end = _First2;
            _Nodeptr _Run_end;
            for (;;) {
                _Run_end = _BRun_end->_Next;
                if (_BRun_end == _BLast) {
                    break;
                }

                if (!_DEBUG_LT_PRED(_Pred, _Run_end->_Myval, _First1->_Myval)) {
                    // _Run_end is the first element in (_BMid->_Myval, _BLast->_Myval) that shouldn't precede
                    // _First1->_Myval.
                    // After the splice _First1->_Myval will be in position and must not be compared again.
                    break;
                }

                _BRun_end = _Run_end;
            }

            _BMid->_Next     = _Run_end; // snip out the run from its old position
            _BFirst1->_Next  = _First2; // insert into new position
            _BRun_end->_Next = _First1;
            if (_BRun_end == _BLast) {
                return _BMid;
            }

            _BFirst1 = _First1;
            _First2  = _Run_end;
        }
    }

uj5u.com熱心網友回復：

歸并排序的“自下而上”變體可以在 O(n log n) 時間和 O(1) 空間內對鏈表進行排序。請參閱維基百科文章。如果不需要 O(1) 空間，那么您可以在串列中構造一個指標陣列，使用任何 O(n log n) 排序演算法對其進行排序，然后從排序后的副本重建串列。

標籤：C 排序 stl

上一篇：為什么我的javascript排序函式沒有產生正確的順序？

下一篇：python中的排序鏈接