stl和.net基础库默认搜索使用哪种排序算法？
我现在正在研究合并排序的简化版本。 我用C++和C#实现了它。 然后分别与stl sort和array.sort()算法进行比较。 在 C++ 中，我得到了相同（有时更好）的结果。 但在 C# 中，我必须使用不安全的代码来使用指针。 这里的性能与默认排序没有太大可比性。 所以，我想知道-
1、stl和.net基类库使用了哪些算法？（有链接更好）
2.不安全的代码是否存在性能问题？
3. 对于衡量新算法的性能，您有什么建议吗？
I am now working on an imprived version of merge sort. I implemented it with C++ and C#. Then compared them with the stl sort and array.sort() algorithm respectively. In C++ I have got an equal (sometimes better) result. But in C#, I had to use unsafe code for using pointers. Here the performence is not that much comparable with default sort. So, I want to know-
1. Which algorithms are used in stl and .net base class library?(Better with links)
2. Do unsafe codes has performence issues?
3. Any suggessions for me regarding measuring the performence of the new algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
.NET 使用快速排序的变体（Sedgewick 的中位数为 3 的快速排序）。
除非您是排序方面的专家，否则如果您可以在广泛的数据（包括随机、已排序和逆序集）上击败内置排序，我会感到惊讶。 诉诸不安全的代码通常是一个坏主意......
.NET uses a variation of Quicksort (Sedgewick's median of 3 Quicksort).
Unless you are an expert in sorting, I would be surprised if you can beat the built-in Sort over a wide range of data (including random, already ordered and reverse ordered sets). Resorting to unsafe code is usually a bad idea...
STL 排序可能取决于实现，但是（正如维基百科所述) 它通常是introsort，快速排序和堆排序的组合。 它的平均复杂度必须为 O(n log n) 比较。
The STL sort may depend on the implementation, but (as wikipedia says) it is usually introsort, a combination of quicksort and heapsort. It must have an average complexity of O(n log n) comparisons.
.NET 使用快速排序。 可以使用 Reflector 查看 System.Collections.Generic.ArraySortHelper 中的
实现大多数情况下，QuickSort 会比 MergeSort 运行得更快，即使最坏情况的执行时间更长。 我认为标准快速排序也有一些改进，但我不确定是否使用了其中任何一个。
我似乎还记得STL也使用QuickSort，但我不完全确定。
.NET uses QuickSort. You can use Reflector to view the implementation in System.Collections.Generic.ArraySortHelper
In most cases, QuickSort will run faster than MergeSort, even though the worst-case execution time is longer. There have been some improvements on standard QuickSort as well I think, but I'm not certain if any of these are used.
I seem to recall STL using QuickSort as well, but I'm not completely certain.