C++ algorithm Sorting

C++ algorithm

字数统计: 2.4k阅读时长: 11 min

 2021/05/21   Share

C++ algorithm Sorting

这一部分是有关于排序的。

函数名	函数功能
sort	对范围内的元素进行排序（不稳定）
stable_sort	对范围内的元素进行排序（稳定）
partial_sort	排序部分范围内的元素
partial_sort_copy	排序并复制部分范围内的元素
is_sorted	检查范围是否已排序
is_sorted_until	查找范围内的第一个未排序元素
nth_element	对范围内的元素进行排序（特殊）

sort

将 [first,last) 范围中的元素按升序排序。

不保证等效元素保持其原始相对顺序。（排序不稳定）

sort 共有两个版本：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 Compare 方法
template <class _RanIt, class _Pr>
void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last), using _Pred
    _Adl_verify_range(_First, _Last);
    const auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast  = _Get_unwrapped(_Last);
    _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pass_fn(_Pred));
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第三参数的比较方式。
template <class _RanIt>
void sort(const _RanIt _First, const _RanIt _Last) { // order [_First, _Last), using operator<
    _STD sort(_First, _Last, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

stable_sort

将范围中的元素 [first,last) 按升序排序。

保证等效元素保持其原始相对顺序。（排序稳定）

stable_sort 共有两个版本：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 Compare 方法
template <class _BidIt, class _Pr>
void stable_sort(const _BidIt _First, const _BidIt _Last, _Pr _Pred) {
    // sort preserving order of equivalents, using _Pred
    _Adl_verify_range(_First, _Last);
    const auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast  = _Get_unwrapped(_Last);
    const auto _Count  = _STD distance(_UFirst, _ULast);
    if (_Count <= _ISORT_MAX) {
        if (_Count > 1) {
            _Insertion_sort_unchecked(_UFirst, _ULast, _Pass_fn(_Pred));
        }

        return;
    }

    _Optimistic_temporary_buffer<_Iter_value_t<_BidIt>> _Temp_buf{_Count - (_Count >> 1)};
    _Stable_sort_unchecked(_UFirst, _ULast, _Count, _Temp_buf._Data, _Temp_buf._Capacity, _Pass_fn(_Pred));
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第三参数的比较方式。
template <class _BidIt>
void stable_sort(const _BidIt _First, const _BidIt _Last) { // sort preserving order of equivalents, using operator<
    _STD stable_sort(_First, _Last, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

sort 和 stable_sort 的区别：

sort 排序不稳定，stable_sort 排序稳定。

partial_sort

重新排列范围 [first,last) 中的元素，以使 middle 之前的元素是整个范围中的最小元素，并按升序排序，而其余元素则没有任何特定顺序。

partial_sort 共有两个版本：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 middle 迭代器，第三参数为 last 迭代器，第四参数为 Compare 方法
template <class _RanIt, class _Pr>
void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred) {
    // order [_First, _Last) up to _Mid, using _Pred
    _Adl_verify_range(_First, _Mid);
    _Adl_verify_range(_Mid, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _UMid  = _Get_unwrapped(_Mid);
    const auto _ULast = _Get_unwrapped(_Last);

    if (_UFirst == _UMid) {
        return; // nothing to do, avoid violating _Pop_heap_hole_unchecked preconditions
    }

    _Make_heap_unchecked(_UFirst, _UMid, _Pass_fn(_Pred));
    for (auto _UNext = _UMid; _UNext < _ULast; ++_UNext) {
        if (_DEBUG_LT_PRED(_Pred, *_UNext, *_UFirst)) { // replace top with new largest
            _Iter_value_t<_RanIt> _Val = _STD move(*_UNext);
            _Pop_heap_hole_unchecked(_UFirst, _UMid, _UNext, _STD move(_Val), _Pass_fn(_Pred));
        }
    }

    _Sort_heap_unchecked(_UFirst, _UMid, _Pass_fn(_Pred));
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第四参数的比较方式。
template <class _RanIt>
void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last) { // order [_First, _Last) up to _Mid, using operator<
    _STD partial_sort(_First, _Mid, _Last, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

示例：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	vector<int> a{ 3,4,1,2,5 };
	partial_sort(a.begin(), a.begin() + 2, a.end());
	for (int& t : a) {
		cout << t << " ";
	}

	return 0;
}

输出：

1 2 4 3 5

partial_sort_copy

将 [first,last) 范围内的最小元素复制到 [result_first,result_last) ，对复制的元素进行排序。复制的元素数目为 min (result_first - result_last, first - last) 。

原 [first,last) 不会产生变化。

partial_sort_copy 共有两个版本：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 result_first 迭代器，第三参数为 result_last 迭代器，第五参数为 Compare 方法
template <class _InIt, class _RanIt, class _Pr>
_RanIt partial_sort_copy(_InIt _First1, _InIt _Last1, _RanIt _First2, _RanIt _Last2, _Pr _Pred) {
    // copy [_First1, _Last1) into [_First2, _Last2) using _Pred
    _Adl_verify_range(_First1, _Last1);
    _Adl_verify_range(_First2, _Last2);
    auto _UFirst1      = _Get_unwrapped(_First1);
    const auto _ULast1 = _Get_unwrapped(_Last1);
    auto _UFirst2      = _Get_unwrapped(_First2);
    const auto _ULast2 = _Get_unwrapped(_Last2);
    auto _UMid2        = _UFirst2;
    if (_UFirst1 != _ULast1 && _UFirst2 != _ULast2) {
        for (; _UFirst1 != _ULast1 && _UMid2 != _ULast2; ++_UFirst1, (void) ++_UMid2) {
            *_UMid2 = *_UFirst1; // copy min(_ULast1 - _UFirst1, _ULast2 - _UFirst2)
        }

        _Make_heap_unchecked(_UFirst2, _UMid2, _Pass_fn(_Pred));
        for (; _UFirst1 != _ULast1; ++_UFirst1) {
            if (_DEBUG_LT_PRED(_Pred, *_UFirst1, *_UFirst2)) {
                // replace top with new largest:
                _Pop_heap_hole_by_index(_UFirst2, static_cast<_Iter_diff_t<_RanIt>>(0),
                    static_cast<_Iter_diff_t<_RanIt>>(_UMid2 - _UFirst2), static_cast<_Iter_value_t<_InIt>>(*_UFirst1),
                    _Pass_fn(_Pred));
            }
        }

        _Sort_heap_unchecked(_UFirst2, _UMid2, _Pass_fn(_Pred));
    }

    _Seek_wrapped(_First2, _UMid2);
    return _First2;
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第五参数的比较方式。
template <class _InIt, class _RanIt>
_RanIt partial_sort_copy(_InIt _First1, _InIt _Last1, _RanIt _First2, _RanIt _Last2) {
    // copy [_First1, _Last1) into [_First2, _Last2), using operator<
    return _STD partial_sort_copy(_First1, _Last1, _First2, _Last2, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

这个函数有个有意思的地方，居然有返回值，返回的是复制序列的开头位置。

示例：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	vector<int> a{ 3,4,1,2,5 };
	vector<int> b{ 0,0,0 };
	partial_sort_copy(a.begin(), a.end(), b.begin(), b.end());
	for (int& t : b) {
		cout << t << " ";
	}

	return 0;
}

输出：

1 2 3

is_sorted

检查 [first,last) 范围内是否有序。

is_sorted 共有两个版本：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 Compare 方法
template <class _FwdIt, class _Pr>
_NODISCARD bool is_sorted(_FwdIt _First, _FwdIt _Last, _Pr _Pred) { // test if range is ordered by predicate
    _Adl_verify_range(_First, _Last);
    const auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast  = _Get_unwrapped(_Last);
    return _STD is_sorted_until(_UFirst, _ULast, _Pass_fn(_Pred)) == _ULast;
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第三参数的比较方式。
template <class _FwdIt>
_NODISCARD bool is_sorted(_FwdIt _First, _FwdIt _Last) { // test if range is ordered by operator<
    return _STD is_sorted(_First, _Last, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

is_sorted_until

查找 [first,last) 范围内的第一个未排序元素。

is_sorted_until 共有两个版本：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 Compare 方法
template <class _FwdIt, class _Pr>
_NODISCARD _FwdIt is_sorted_until(const _FwdIt _First, _FwdIt _Last, _Pr _Pred) {
    // find extent of range that is ordered by predicate
    _Adl_verify_range(_First, _Last);
    auto _UFirst = _Get_unwrapped(_First);
    auto _ULast  = _Get_unwrapped(_Last);
    if (_UFirst != _ULast) {
        for (auto _UNext = _UFirst; ++_UNext != _ULast; ++_UFirst) {
            if (_DEBUG_LT_PRED(_Pred, *_UNext, *_UFirst)) {
                _ULast = _UNext;
                break;
            }
        }
    }

    _Seek_wrapped(_Last, _ULast);
    return _Last;
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第三参数的比较方式。
template <class _FwdIt>
_NODISCARD _FwdIt is_sorted_until(_FwdIt _First, _FwdIt _Last) { // find extent of range that is ordered by operator<
    return _STD is_sorted_until(_First, _Last, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

nth_element

重新排列 [first, last) 中的元素。使得 nth 之前的元素都不大于该元素，nth 之后的元素都不小于该元素。（C++ 17）

但是 nth 不能等于 last。如果 nth 等于 last 则函数调用无效。

nth_element 共有两个版本：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 nth 迭代器，第三参数为 last 迭代器，第四参数为 Compare 方法
template <class _RanIt, class _Pr>
void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred) { // order Nth element, using _Pred
    _Adl_verify_range(_First, _Nth);
    _Adl_verify_range(_Nth, _Last);
    auto _UFirst     = _Get_unwrapped(_First);
    const auto _UNth = _Get_unwrapped(_Nth);
    auto _ULast      = _Get_unwrapped(_Last);
    if (_UNth == _ULast) {
        return; // nothing to do
    }

    while (_ISORT_MAX < _ULast - _UFirst) { // divide and conquer, ordering partition containing Nth
        auto _UMid = _Partition_by_median_guess_unchecked(_UFirst, _ULast, _Pass_fn(_Pred));

        if (_UMid.second <= _UNth) {
            _UFirst = _UMid.second;
        } else if (_UMid.first <= _UNth) {
            return; // Nth inside fat pivot, done
        } else {
            _ULast = _UMid.first;
        }
    }

    _Insertion_sort_unchecked(_UFirst, _ULast, _Pass_fn(_Pred)); // sort any remainder
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第四参数的比较方式。
template <class _RanIt>
void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last) { // order Nth element, using operator<
    _STD nth_element(_First, _Nth, _Last, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

示例：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	vector<int> a{ 3,4,5,2,1 };
	nth_element(a.begin(), a.begin() + 2, a.end());
	for (int& t : a) {
		cout << t << " ";
	}

	return 0;
}