探索一些标准库排序功能
在今天的文章中，我们将探讨一些排序功能。 这些是我们作为开发人员在几乎所有日常任务中使用的非常常见的功能。 我们将探索clang libc ++的一些函数，例如std :: sort，std :: stable_sort和std :: partial_sort。 另外，我们将研究其中一些函数的算法，并尝试了解它们的工作原理。 另外，我们将讨论Swift Collection排序方法\ o /。
使用排序算法时，我们要了解的最重要的事情之一就是时间复杂度。 幸运的是，此信息始终是这些方法文档的一部分，因此在调用标准库排序方法时，我们具有此保证。
分类
std :: sort是使用Introsort算法的排序函数，其复杂度为O（N log（N）），其中N = std :: distance（first，last）自C ++ 11起，且元素顺序相等不能保证保留[3]。 gcc-libstdc ++也使用Introsort算法。
Introsort是一种混合算法，基本上使用两种（或在某些实现中为三种）算法来优化运行时复杂性。 它开始使用Quicksort，并且如果递归深度超出接近O（N log（N））[1]的阈值，它将切换到Heapsort算法，以避免Quicksort最坏情况下具有O（N²）的情况。时间复杂度。 在某些实现中，它使用InsertionSort在排序过程中对小区域进行排序，因为在这种情况下，它的处理效率更高。
我们没有详细介绍Introsort算法的实现细节，但是您可以在[7]上看到伪代码，该伪代码显示了其背后的逻辑。
在下面，我们可以看到一个非常简单的示例，说明如何使用std :: sort对int向量进行升序和降序排序。
这就是本文的全部，希望您喜欢🙂
如果我有问题或您有任何意见或疑问，请告诉我。 我很高兴收到您的反馈feedback
您可以在Twitter上@ LucianoPassos11找到我。
感谢您阅读🙂
参考文献
- 2017年LLVM开发人员会议：A.基于Kumar Introsort的libc ++排序功能。 https://www.youtube.com/watch?v=Lcz0ZHewkHs
- “ libc ++” C ++标准库。 https://libcxx.llvm.org
- std :: sort — cppreference.com。 https://en.cppreference.com/w/cpp/algorithm/sort
- std :: stable_sort — cppreference.com.https：//en.cppreference.com/w/cpp/algorithm/stable_sort
- std :: partial_sort — cppreference.com。 https://en.cppreference.com/w/cpp/algorithm/partial_sort
- 了解您的排序算法| 设置2（Introsort- C ++的排序武器）https://www.geeksforgeeks.org/know-your-sorting-algorithm-set-2-introsort-cs-sorting-weapon/
- 维基百科Introsort https://en.wikipedia.org/wiki/Introsort
- 快速排序。 https://www.geeksforgeeks.org/quick-sort/
- 堆排序。 https://www.geeksforgeeks.org/heap-sort/
- 合并排序。 https://www.geeksforgeeks.org/merge-sort/
- 合并排序| 极客 https://www.youtube.com/watch?v=JSceec-wEyw
- 插入排序。 https://www.geeksforgeeks.org/insertion-sort/
- Musser，David R .：自省式排序和选择算法。 http://www.cs.rpi.edu/~musser/gp/introsort.ps