STL的list :: sort（）使用哪种排序算法？

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一个随机整数列表。我想知道该list::sort()方法使用哪种算法。例如下面的代码：

list<int> mylist;
// ..insert a million values
mylist.sort();

回答：

该标准不需要特定的算法，只要求它必须稳定，并使用大约N lg

N个比较来完成排序。例如，这允许使用快速排序的合并排序或链接列表版本（与流行的看法相反，快速排序 不一定是 不稳定的，即使最常见的数组实现是）。

有了这个条件，简短的答案是，在大多数当前的标准库中，它std::sort是作为一个intro-

sort（自省排序）实现的，它基本上是一个Quicksort，可以跟踪其递归深度，并将切换到Heapsort（通常速度较慢，但​​是如果Quicksort使用的递归深度过深，则可以保证O（n

log n）的复杂性。Introsort是相对较新的发明（1990年代后期）。较旧的标准库通常使用Quicksort代替。

stable_sort之所以存在这个问题是因为，对数组状容器进行排序时，大多数最快的排序算法都是不稳定的，因此该标准既包括std::sort（快速但不一定稳定）又包括std::stable_sort（稳定但通常较慢）。

但是，这两种方法通常都希望使用随机访问的迭代器，并且对于链表之类的东西工作不佳（如果有的话）。为了使链表具有良好的性能，该标准包括list::sort。但是，对于链表，实际上并没有任何权衡取舍-

实现既稳定 又与 其他任何东西一样快的合并排序很容易。这样，他们只需要一个sort稳定的成员函数即可。

以上是 STL的list :: sort（）使用哪种排序算法？ 的全部内容， 来源链接： utcz.com/qa/420712.html

回到顶部