gpt4 book ai didi

c++ - 选择排序与数组和链表的区别?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:01:27 28 4
gpt4 key购买 nike

我想知道使用带有 findmax 的数组和带有 findmin 的链表的选择排序背后的逻辑是什么。两者的最佳和最坏情况?

最佳答案

长话短说

选择排序通常很糟糕。合并排序通常很好,但可以通过 std::sort 改进随机访问容器和成员函数 sort() 改进基于节点的容器。

选择排序以二次方式缩放

考虑以下通用版本的selection_sort

template<class ForwardIt, class Compare = std::less<typename std::iterator_traits<ForwardIt>::value_type>>
void selection_sort(ForwardIt first, ForwardIt last, Compare cmp = Compare())
{
for (auto it = first; it != last; ++it) {
auto const selection = std::min_element(it, last, cmp);
std::iter_swap(selection, it);
}
}

在长度为 Nstd::arraystd::list 上,它有 O(N^2) 复杂度:外层循环处理所有 N 元素,内部调用 std::min_element 也是线性复杂度,这给出了整体二次缩放。

但是,由于基于比较的排序可以像 O(N log N) 一样便宜地完成,所以对于大的 N,这是通常 Not Acceptable 缩放>。正如@EJP 所提到的,选择排序的一个可取之处是尽管它进行O(N^2) 比较,但它只进行O(N) 数据交换。然而,对于非常大的 N,这个优于大多数 O(N log N) 排序算法的优势最终会被 O(N^2) 比较成本。

通用归并排序来拯救?

考虑以下通用版本的 merge_sort

template<class BiDirIt, class Compare = std::less<typename std::iterator_traits<BiDirIt>::value_type>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare())
{
auto const N = std::distance(first, last);
if (N < 2) return;
auto middle = first + N / 2;
merge_sort(first, middle, cmp);
merge_sort(middle, last, cmp);
std::inplace_merge(first, middle, last, cmp);
}

在长度为 Nstd::arraystd::list 上,它有 O(N log N) 复杂性:递归深度为 O(log N)(因为间隔每次都被减半)并且对 std::inplace_merge 的调用是线性复杂度,这给出了整体 O(N log N) 缩放比例。

但是,几乎任何严肃的排序算法竞争者都不会通过比较次数来区分自己,而是通过访问和放置数据的相关开销来区分自己。此类优化只能通过比通用版本更多的知识来完成。

随机访问容器可以受益于混合算法

使用混合算法可以更便宜地对具有随机访问迭代器的容器进行排序。标准库中的 std::sort()std::stable_sort 函数提供了这种 O(N log N) 最差的混合算法-案例复杂性。通常它们作为 IntroSort 实现,它将递归随机枢轴快速排序与堆排序和插入排序混合,具体取决于各种递归排序子范围的大小。

基于节点的容器可以受益于成员函数 sort()

基于比较的排序算法大量使用复制或交换迭代器指向的基础数据。对于常规容器,交换底层数据是您能做的最好的事情。对于基于节点的容器,例如 std::liststd::forward_list,您更愿意拼接:仅重新排列节点指针和避免复制潜在的大量数据。但是,这需要了解迭代器之间的连接。

这就是为什么 std::liststd::forward_list 都有一个成员函数 sort():它们具有相同的 O(N log N) 最坏情况复杂度,但利用了容器的基于节点的特性。

关于c++ - 选择排序与数组和链表的区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18137925/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com